《计算机软件技术编程基础 链表》由会员分享，可在线阅读，更多相关《计算机软件技术编程基础 链表（43页珍藏版）》请在金锄头文库上搜索。
1、顺序表的 特点：运算：简单，时间复杂度好存储特性：静态规模，编译前确定问题：程序的通用性和空间利用率之间的矛盾期望：在实际运行过程中，根据实际问题的需要临时确定存 储空间，涉及到动态变量动态变量：在程序运行的过程中产生和释放的变量。与之相 反的是静态变量静态变量：在程序运行的过程中一直存在的变量。静态变量是出现在说明语句中的变量；动态变量由于是在运行中产生的，因而不会事先说明如何实现动态变量？通过指针来实现：指针变量的说明，动态变量的产生和释放 。2.3 线性链表及其运算线性表的链式存储结构称为线性链表，即将表中元素用 链地址连接起来。 head头 指 针结 点对线性表中的每一个数据元素，都需
2、用两部分来存储：一部分用于存放数据元素值，称为数据域；另一部分用于存放直接前驱或直接后继结点的地址（指针），称为指针域，称这种存储单元为结点。 链表的存储结构链式存储结构是利用任意的存储单元来存放线性表中的元素，存储数据的单元在内存中可以连续，也可以零散分布。由于线性表中各元素间存在着线性关系，每一个元素有一个直接前驱和一个直接后继。为了表示元素间的这种线性关系，在这种结 构中不仅要存储线性表中的元素，还要存储表示元素之间逻辑关系 的信息。所以用链式存储结构表示线性表中的一个元素时至少需要 两部分信息，除了存储每一个数据元素值以外，还需存储其后继或 前驱元素所在内存的地址。两部分信息一起构成链
3、表中的一个结点 。结点的结构如下所示。链表结构示意图从图中可见，每个结点的存储地址存放在直接前驱的指针域中 。所以要访问链表中数据元素C，必须由头指针head得到第一个结点（数据A）的地址，由该结点的指针域得到第二个结点（数据B） 的地址，再由其指针域得到存储数据C的结点地址，访问该结点的数 据域就可以处理数据C了。链表这种顺着指针链依次访问数据元素的特点，表明链表是一种顺序存储结构，只能顺序操作链表中元素。不 能像顺序表（数组）那样可以按下标随机存取。在链表存储结构中，不要求存储空间的连续性，数据元素之间的逻辑关系由指针来确定。每个结点由两部分组成：data 数据域存放数据值next指针域存
4、放后继结点的首地址链表通过每个指针域将n个结点按逻辑次序链接成一个整体。float score; student *next; ;struct ListNodeELEM data；ListNode *next;1 672 873 794 86headtail/建立链表 linklist *create() linklist *head,*p1,*p2;head=NULL;int x; cinx;struct linklist int num; float score; linklist *next; ;p2=p1; /将新的结点作为尾结点 p2-next=NULL; cinx; while(x
5、0)p1=new(linklist); p1-num=x; cinp1-score;n=n+1;if(head=NULL)head=p1;else p2-next=p1;建立链表的条件void print( ) coutnumscore; coutnext; while (p1!=NULL); 查找运算 的实现设计思路：设置一个跟踪链表结点的指针p1，初始时 p1指向链表中的第一个结点，然后顺着next域依次指 向每个结点，每指向一个结点就判断其值是否等于i，若 是则返回该结点地址,否则继续往后搜索.要访问单链表中第i个元素值，必须从头指针开始遍历链表 ，依次访问每个结点，直到访问到第i个结点
6、为止。其时 间复杂度为O(n)。linklist *getnode else coutnum!=i j+;如果该结点不是要 找的结点？if(p1-num=i) j+; cout n e xtP1 - n ex t删除条件if(p1-num=num)if(p1=head) head=p1-next; else p2-next=p1-next; n=n-1; else cout n e x tP1 - ne xtwhile(p1-num!=num p1=p1-next;如果该结点不是要 找的结点？找到该结点如何删除？线性链表的插入：在链式存储结构下的线性表中插入一个新结点在头指针head的线性链表
7、中包含元素x的结点之前加入一个新结点void inslst(linklist *head, int x) linklist *p1,*p2; p1=new(linklist); cinp1-nump1-score; if(head=NULL) head=p1; p1-next=NULL; p2=getnode(head,x);/寻找包含元素x的结点nextnextp1P2-nextp2p1-next=p2-next;/将结点p1插入到结点p2后 p2-next=p1;在插入和删除算法中，都是先查询确定操作位置，然 后再进行插入和删除操作。所以其时间复杂度均为 O(n)。另外在算法中实行插入和删
8、除操作时没有移 动元素的位置，只是修改了指针的指向，所以采用链 表存储方式要比顺序存储方式的效率高循环链表循环链表是单链表的另一种形式，是一个首尾相接的链表。 特点：最后一个结点的指针域不空，而是指向头结点，整个 链表连成环状，从表中任意结点出发均可到达其他结点。其余函数运算没有变化，请自行写出相关函数的定义。 在循环链表中，除了有头指针head外，有时还可加上一个尾指针 tail。尾指针tail指向最后一结点，沿最后一个结点的指针又可立 即找到链表的第一个结点。在实际应用中，使用尾指针来代替头 指针进行某些操作往往会更简单。 【例】将两个循环链表首尾相接进行合并，La为第一个循环链表表尾 指
9、针，Lb为第二个循环链表表尾指针，合并后Lb为新链表的尾指 针，head指向整个合并后的链表。 【解】算法思路：对两个单循环链表La，Lb进行的连接操作，是将Lb的第一个数 据结点接到La的尾部。操作时需要从La的头指针开始找到La的 尾结点，其时间复杂性为O(n)。而在循环链表中若采用尾指针 La，Lb来标识，则时间性能将变为O(1)。其连接过程如图2- 14所示。图 两个循环链表首尾相接进行合并 (a)连接前p=La-next;q=Lb-next(b)连接后La-next=q;Lb-next=p;a1a2aianb1b2bibnLaLbpqLbLaa1a2aianb1b2bibn双向链表n
10、extdataprior双向链表的结点结构struct dlnodeELEM data；dlnode *next, *prior;对结点p而言，后继结点的地址p-next;前驱结点的地址p-priordatapp1p0P-prior-nextP-next-priorP-priorP-nextsp1p0P1-prior-next=sP1-prior=ss-prior=p1-priors-next=p1双向链表中结点的插入将结点s的插入结点p1之前pP-nextP-prior双向链表中结点的删除P-prior-next=p-nextP-next-prior=p-priordelete P应用举例
11、一元多项式相加假设用单链表表示多项式：A(x)=12+7x+8x10+5x17 ， B(x)=8x+15x7-6x10，头指针Ah与Bh分别指向这两个链表， 如图2-21所示：对两个多项式进行相加运算，其结果为C(x)= 12+15x+15 x7+2x10+5x17。如图所示。图 合并以前的链表图 2-22 合并以后的链表8115 760Bh12 0718105 17Ah15 115 72 105 17012Ch对两个一元多项式进行相加操作的运算规则是：假设指针qa 和qb分别指向多项式A(x)和B(x)中当前进行比较的某个结点，则需比较两个结点数据域的指数项，有三种情况：(1) 指针qa所指
12、结点的指数值指针qb所指结点的指数值时，则保 留qa指针所指向的结点，qa指针后移；(2) 指针qa所指结点的指数值指针qb所指结点的指数值时，则将 qb指针所指向的结点插入到qa所指结点前，qb指针后移；(3) 指针qa所指结点的指数值指针qb所指结点的指数值时，将两个结点中的系数相加。若和不为零，则修改qa所指结点的系数值，同时释放qb所指结点；反之，从多项式A (x)的链表中删除相应结点，并释放指针qa和qb所指结点。多项式相加算法： struct polynode *add_poly(polynode *Ah, polynode *Bh) polynode *qa,*qb,*s,*r,
13、*Ch; qa=Ah;qb=Bh; /qa和qb分别指向两个链表的第一结点 r=qa;Ch=Ah; /将链表Ah作为相加后的结果链表 while(qa!=NULLif(x!=0) qa-coef=x;r-next=qa;r=qa;s=qb+;free(s);qa+; /相加后系数不为零时elses=qa+;free(s);s=qb+;free(s); /相加后系数为零时else if(qa-expexp) r-next=qa;r=qa;qa+; /多项式Ah的指数值小elser-next=qb;r=qb;qb+;/多项式Bh的指数值小链栈top栈顶链表的头部作栈顶是最方便的 链表的头指针叫做栈
14、顶指针 只允许在表头进行插入和删除运算struct linkstack int num; float score; linkstack *next; ;/置空栈 linkstack *init_linkstack() return NULL; /判断栈空 int empty_linkstack(linkstack *top) if(top=NULL) return 1; else return 0; /入栈 linkstack *push_linkstack(linkstack *top, linkstack *stud) stud-next=top; top=stud; n=n+1; ret
15、urn top; topstudtoptop/出栈linkstack *pop_linkstack(linkstack *top, linkstack *stud) if(top=NULL) return NULL; else stud=top; top=top-next; n=n-1; return top; toptopstud带链的队列rearfront先进先出的数据结构只允许在表头删除，表尾插入的单链表struct qnode int num; struct qnode *next; ;struct lqueue qnode *front,*rear; ;lqueue *init_lqueue() lqueue *l; qnode *q; l=new(lqueue); q=new(qnode); q-next=NULL; l-front=l-rear=q; return l; 创建一个空队列frontrearnextstruct qnode int num; struct qnode *next; ;struct lqueue qnode *fro
