数据结构CC++循环链表ppt课件

1、有一个单链表L(至少有一个结点)，其头结点指针为head，编写一个函数将L逆置，即最后一个结点变成第1个结点，原来倒数第二个结点变成第二个结点如此等等。解：本题采用的算法是，从头到尾遍历单链表L，并设置3个附加指针p、q、r,p指向当前处理的结点，q指向p的下一个结点，r指向q的下一个结点，q、r的作用是为了防止倒置指针时，下一个结点的丢失而设置的，有了这三个指针，就可以方便地实现指针的倒置。最后将第一个结点的next域置为NULL，并将头指针指向最后一个结点，这样达到了本题的要求。 void invert( linklist head) linklist p, q, r; p=head; q

2、=p-next; while(q!=NULL) /*没有后继时停止*/ r=q-next; q-next=p; p=q; q=r; head-next=NULL; head=p; typedef struct node datatype data; struct node *next;*linklist;堆栈的最简单的表示方法是采用一维数组，为形象起见，一般在图中将堆栈画成竖直的 。设数组名为data，其下标的下界为0，上界为n。一般需用一个变量top记录当前栈顶的下标值，top也叫做栈指针。topADCB3642105data本例中top=4 在C语言中通常用以下方式定义一个顺序栈结构体：#

3、define N 30Typedef struct stackdatatype data N ; Int top;sqstack;入栈push） 入栈的主要操作是先将栈顶指针加1；然后将入栈元素放到栈顶指针所指示下值的位置上。设用指针P表示堆栈，入栈的元素值为x，则可得到入栈函数如下：#define N 30Typedef struct stackdatatype data N ; Int top;sqstack;void push ( sqstack *p, datatype x) if (p-top=N-1) printf(“栈溢出!n”); /*显示栈满信息*/ else (p-top)

4、+; p-datap-top=x; #define N 30Typedef struct stackdatatype data N ; Int top;sqstack;void pop (sqstack *p) if (p-top= -1) printf(“空栈!n”); /*栈为空显示相应的信息*/ else x=p-datap-top; ( p- top)-; /*栈顶位置下移*/ return x; 2. 出栈Pop）出栈运算时，先将栈顶的元素值赋给某个变量，以备后面的运算应用；然后栈顶指针减1，将栈顶位置下移。假设已指定的变量为x，则出栈的函数如下： 链堆栈是栈的链接存储表示，它是只允

5、许在表头进行插入和删除运算的单链表。它与普通的单链表没有什么不同，只是将头指针head改称为栈顶指针top。 top 在栈顶指针是top的链堆栈中插入一个值为x的结点的算法：void push (linklist top, datatype x) linklist s; s=new node ; /*建立一个结点指针*/ s-data=x; s-next=top; top=s; int pop(linklist top) int x; linklist p; if( top= = NULL) coutdata; p=top; top=top-next; delete p; return x;

6、循环链表circular linked list是一种首尾相接的链表，将单链表表尾结点原来的空指针改为指向表头结点，就成为循环链表。循环链表并不多占存储单元，但从循环链表的任一个结点出发都可以访问到此链表的每一个结点，因为当访问到表尾结点后又能返回到头结点。 head 有两个循环单链表，头指针分为head1和head2，编写函数将链表head2链接到链表head1之后，链接后的链表仍保持是循环链表的形式。解：先分别找到两个链表的表尾，将head2放入链表head1的表尾，将两个链表链接起来，然后将head1放入原head2链表的表尾，构成新的循环链表。 head1 a1 an a2 head2

7、 b1 bn b2 link(linklist head1,head2) linklist p, q; p=head1; while(p-next!=head1) p=p-next; q=head2; while(q-next!=head2) q=q-next; p-next=head2; q-next=head1; 通常在循环链表的表头结点前面再加一个空结点,也叫空表头结点。表空时空表头结点的指针指向其本身，如下面的图所示为空循环链表。 空表头结点除指针以外的数据域是没有用的，但为了将此结点与一般结点相区别，常常是将其赋以一个特别的数据，以与一般结点相区别。 head 另一种方法是不设头指针

8、而改设尾指针，这样无论是找头结点还是尾结点都很方便。因为尾结点由尾指针rear来指示，则头结点的位置是rear-next-next。 rear rear 双向链表中每个结点除了有向后指针外，还有指向其前一个结点的指针，这样形成的链表中有两条不同方向的链，因此从某一结点均可向两个方向访问。 双链表的结点形式为： 其中链域prior和next分别指向本结点的直接前趋和直接后继结点。 prior data next 如果循环链表的结点再采用双向指针，就成为双向循环链表。 head 双链表较单链表虽然要多占用一些存储单元，但对其插入和删除操作以及查找结点的前趋和后继都非常方便。 双链表结构是一种对称结

9、构，设指针p指向双链表的某一结点，则双链表的对称性可用下式来表示： p=(p-prior)-next=(p-next)-prior 即结点*p的地址既存放在其前趋结点 *(p-prior)的后继指针域中，又存放在它的后继结点*(p-next)的前趋指针域中。 设要在p所指结点的前面插入一个新结点*q，则需要修改4个指针 ：q-prior=p-prior; q-next=p; (p-prior)-next=q; p-prior=q; p q 设p指向待删除的结点，则删除该结点步骤为：(p-prior) -next=p-next; (p-next) -prior=p-prior; 这两个语句的执行

10、顺序可以颠倒，执行这两个语句之后，可调用delete p,将*p结点释放。 p 前往在十字链表中，矩阵的每个非零元素对应着一个含有五个域的结点，这五个域分别为该非零元素在稀疏矩阵中的行号、列号、元素的数值以及两个指针，其中一个指针指向同一列的下一个非零元素的结点，另一个指针指向同一行的右边一个非零元素的结点。 行号 列号 数值 向右指针 向下指针 将每行的非零元素结点链接成循环链表，又将每列的非零元素结点链接成循环链表，就构成了十字形的链接结构。对于每行、每列的循环链表都有一个空表头结点，以利于元素的插入和删除运算。这些空表头结点的行号、列号都标成零，以便和其它结点相区别。整个十字链表有一个总的空表头结点，在一般结点标以行号、列号之处，此结点是标出矩阵的行数m和列数n。有一个指针HM指向这个总的空表头结点。 例：稀疏矩阵M及其对应的十字链表如图所示。60000570000403009008M H1 H2 H3 H4 H5 HM H5 H4 H3 H2 H1 5 4 0 0 0 0 0 0 0 0 0 0 0 0 1 1 8 1 4 9 0 0 0 0 2 3 -3 0 0 5 4 -6 0 0 3 1 4 4 2 7 4 3 -5