1、循環鏈表判斷空循環表的條件：Head = Head->next;NULL=head->next;/ 判斷單鏈表是否為空 僅設尾指針的單循環表1)保存 ha 的位置2)B 表的第一個元素連到A 表的最后一個元素之后3)釋放 hb4)B 表的最后一個元素指向ha5)返回新循環表尾指針LinkList ConnectList_L(LinkList A, LinkList B) LinkList p=A->next;A->next=B->next->next; free(B->next);B->next=p; Return B; 雙向鏈表1.定義 typ

2、edef struct Lnode int data;Struct Lnode *next;Struct Lnode *prior;Lnode, *LinkList;2.插入結點( 1 )生成一個新結點 s( 2 )把 p->prior 賦給 s->prior(3) 使 p->->next 指向 s( 4 ) s->next 指向 p( 5 ) p->prior 指向 sStatus DulListInsert(DulLinklist L, int i, ElemType e) 尋址If(!(s=(DulLinkList)malloc(sizeof(DulN

3、ode) Return ERROR;s->data=e; s->prior=p->prior; p->prior->next=s;s->next=p; p->prior=s; return ok;3刪除e=p_>data;p_>prior->next=p_>next;p_>next_>prior=p_>prior;free(p);作業雙鏈表的創建并打印Input:102030 4050Output102030405050 40 30 20 10鏈表的初始化用法：#include <malloc.h>

4、或#include<stdlib.h >功能：用于向內存申請空間，分配長度為 num_bytes字節的內存塊說明：如果分配成功則返回指向被分配內存的指針，否則返回空指針NULL當內存不再使用時，應使用free()函數將內存塊釋放。調用格式，其對應例子指針名=(指針所指對象的數據類型*)如下：int *p = (int *) malloc ( n* sizeof(int);#include"stdio.h"#include"malloc.h"#include"string.h"typedef struct LNodeint

5、data;struct LNode *next;LNode,*LinkList;/*帶頭結點的尾插法建立單鏈表，返回表頭指針LinkList CREATLIST()int data;LinkList head,s,r;head=(LinkList)malloc(sizeof(LNode); r=head;scanf("%d", &data);while(data!=0)s=(LinkList)malloc(sizeof(LNode); s->data=data;r->next=s;r=s;scanf("%d", &data);

6、malloc (個數*sizeof(指針所指對象的數據類型 )*/返回鏈表的頭指針，類型為 LinkList型/等價于LNode *head, s,r;r為輔助指針/*生成頭結點*/*尾指針初值指向頭結點*/*0為輸入結束符*/*生成新結點*/*新結點插入表尾*/*尾指針r指向新的表尾*/*讀下一結點*/r->next=NULL; return (head);雙向鏈表#include "stdafx.h"#include <stdio.h>#include <malloc.h>#include <string.h>typedef s

7、truct LNode int data;struct LNode *prior;struct LNode *next;LNode,*LinkList;LinkList CREATELIST()int data;LinkList h,s,r;h=(LinkList)malloc( sizeof (LNode); r=h;scanf( "%d",&data);while (data!=0) s=(LinkList)malloc( sizeof (LNode); s->data=data; r->next=s; s->prior=r; r=s;scan

8、f( "%d",&data);r->next=h;h->prior=r;return (h);void PRINTF1(LinkList h)LinkList p,q;p=h->next;q=h->next;while (p!=h)printf( "%d " ,p->data);q=p;p=p->next;while (q!=h)printf( "%d " ,q->data);q=q->prior;printf( "n" );LinkList INSERT(L

9、inkList h)int data;LinkList p,s;s=(LinkList)malloc( sizeof (LinkList); scanf( "%d",&data);s->data=data;p=h->next;while (p->data<data&p!=h)p=p->next;s->prior=p->prior;p->prior->next=s;s->next=p;p->prior=s;return h;void PRINTF(LinkList h)LinkList p,q;

10、p=h->next;q=h->next;while (p!=h)printf( "%d " ,p->data);q=p;p=p->next;while (q!=h)printf( "%d " ,q->data);q=q->prior;printf( "n" );LinkList DELETE(LinkList h)int data;LinkList p,q;p=h->next; scanf( "%d",&data);while (p!=h)if (p->dat

11、a<data)p->prior->next=p->next; p->next->prior=p->prior; q=p;p=p->next; free(q);elsep=p->next;return h;void PRINTF2(LinkList h)LinkList p,q;p=h->next;q=h->next;while (p!=h)printf( "%d " ,p->data); q=p;p=p->next;while (q!=h)"%d " ,q->data);

12、printf( q=q->prior;void main()LinkList h,h1,h2; h=CREATELIST(); PRINTF(h); h1=INSERT(h); PRINTF1(h1); h2=DELETE(h); PRINTF2(h2);藉棧1. 棧的定義棧(stack)是限制僅在表的一端進行插入和刪除運算的線性表。( 1 )插入和刪除的一端是棧頂(top)另一端是棧底( bottom/base)(2) 后進先出的原則( Last in First Out)(3) 判斷空棧 top=bottom/base2. 順序棧typedef struct SEIemtype *b

13、ase;始終指向棧底，若 base=Null則棧不存在；top-SEIemtype *top;/top的初值top=base，插入一個元素，top+，刪除一個元素 int stacksize;/存儲空間的大小 SqStack;( 1)構造一個空棧 SStatus InitStack(SqStack &S)S.base=(SelemType *)malloc(STACK_INIT_SIZE)*sizeof(SElemType);If(!S.base) return ERROR;S.top=S.base;S.stacksize= STACK_INIT_SIZE;return OK;(2)插

14、入新元素 eStatus Push(SqStack &s, SelemType e)if(S.top-S.base>=S.stacksize)/ 棧滿，追加存儲空間 S.base=(SelemType *) realloc(S.base, (S.stacksize+STACKINCREMENT)*sizeof(SelemType);If(!S.base) return ERROR; S.top=S.base+S.stacksize; S.stacksize+= STACKINCREMENT;*(S.top)=e;/ 把 e 存在 top( 先賦值再 +) top+;return

15、OK;建 DulLinkList createDulLinkList()DulLinkList h, s, p;/h 頭指針，s新結點的指針，p標記指針 h=(DulLinkList)malloc(sizeof(DulNode); / 生成一個頭結點 h h->next=h;h->prior=h;p=h;for(i=0;i<5,i+) s=(DulLinkList)malloc(sizeof(DulNode);Printf(“please input data:n”);Scanf(“%d”,&s->data);p->next=s; s->prior=

16、p;p=s;/p 前進一步，為下一次準備 s->next=NULL;p=h->next;把p放回去return(h);(3) 返回棧頂元素Status GetTop(SqStack s, SelemType &e)if(s.top=s.base) / 判斷該棧是否為空Return ERROR;e=*(s.top-1); return OK;(4) 刪除棧頂元素Status Pop(SqStack s, SelemType &e) if(s.top=s.base) /判斷該棧是否為空Return ERROR;e=*（s.top_1）;top-;return OK;Pu

17、sh 1 2 3 4 5Pop 5 4Push 6 7Pop7 6 3 2 1鏈表、棧練習題講義.循環鏈表的主要優點是A）不再需要頭指針了B）從表中任一結點出發都能訪問到整個鏈表C）在進行插入、刪除運算時，能更好的保證鏈表不斷開D）已知某個結點的位置后，能夠容易的找到它的直接前件（06計算機二級B）棧底至棧頂依次存放元素A、B、C、D,在第五個元素 E入棧前，棧中元素可以出棧，則出棧序列可能是 06計算機二級BA）ABCED B）DCBEA C）DBCEA D）CDABE棧通常米用存儲結構是（A）。a）順序存儲結構和鏈表存儲結構b）散列方式和索引方式c）鏈表存儲結構和數組d）線性存儲結構和非線

18、性存儲結構若某線性表中最常用的操作是在最后一個元素之后插入一個元素和刪除第一個元素，則采用（D）存儲方式最節省運算時間a.單鏈表b.僅有頭指針的單循環鏈表 c.雙鏈表d僅有尾指針的單循環鏈表若某線性表中最常用的操作是取第i個元素和找第i個元素的前趨元素，則采用 （B）存儲方式最節省運算時間a.單鏈表 b順序表 c雙鏈表 .d循環鏈表棧是一種線性表，它的特點是 。設用一維數組 A1,n來表示一個棧，An為棧底，用整型變量 T指示當前棧頂位置，AT為棧頂元素。往棧中推入（PUSH 一個新元素時，變量T的值 （減1、加1、不變）；從棧中彈出（POP 一個元素時，變量T的值 （減1、加1、不變）。設棧

19、空時，有輸入序列a, b, c,經過PUSH POP PUSH PUSH POP操作后，從棧中彈出的元素的序列是。（94初程）答案：后進先出減1加1a c設有一個表頭指針為 h的單鏈表。試設計一個算法，通過遍歷一趟鏈表， 將鏈表中所有 結點的鏈接方向逆轉。要求逆轉結果鏈表的表頭指針h指向原鏈表的最后一個結點。Lin kList ReverseList（L in kList h）Lin kList r,m,p;r=h->n ext;m=r->n ext;p=m _>n ext;while（m!=null）m->next=r; /斷開，并指向前一節點r=m;m=p;p=p-

20、>n ext;h->next->next=null; / 使 a1 指向空h->next=r;/h 指向 Anreturn h;鏈表、棧練習題.循環鏈表的主要優點是A）不再需要頭指針了B）從表中任一結點岀發都能訪問到整個鏈表C）在進行插入、刪除運算時，能更好的保證鏈表不斷開D）已知某個結點的位置后，能夠容易的找到它的直接前驅06計算機二級棧底至棧頂依次存放元素A、B、C D，在第五個元素 E入棧前，棧中元素可以岀棧，則岀棧序列可能是A) ABCEDB) DCBEAC) DBCEAD) CDABE06計算機二級B棧通常采用存儲結構是（）。a）順序存儲結構和鏈表存儲結構b）

21、散列方式和索引方式c）鏈表存儲結構和數組d）線性存儲結構和非線性存儲結構A若某線性表中最常用的操作是在最后一個元素之后插入一個元素和刪除第一個元素，則采用（）存儲方式最節省運算時間a.單鏈表b.僅有頭指針的單循環鏈表 c.雙鏈表d僅有尾指針的單循環鏈表D若某線性表中最常用的操作是取第i個元素和找第i個元素的前趨元素，則采用（）存儲方式最節省運算時間a.單鏈表b順序表c雙鏈表.d循環鏈表B棧是一種線性表，它的特點是。設用一維數組 A1,n來表示一個棧，An為棧底，用整型變量T指示當前棧頂位置，AT為棧頂元素。往棧中推入（PUSH 個新元素時，變量 T的值 （減1、力口 1、不變）；從棧中彈出（P

22、OP 一個元素時，變量 T的值（減1、力口 1、不變）。設棧空時，有輸入序列 a，b，c,經過PUSH POP PUSH PUSH POP操作后，從棧中彈出的元素的序 列是 。（94初程）答案：后進先岀減1加1a c設有一個表頭指針為 h的單鏈表。試設計一個算法，通過遍歷一趟鏈表，將鏈表中所有結點的鏈接方向逆轉。要求逆轉結果鏈表的表頭指針 h 指向原鏈表的最后一個結點LinkList ReverseList(LinkList h) LinkList r,m,p;r=h->next; m=r->next; p=m->next;while(m!=null)m->next=r

23、; / 斷開，并指向前一節點 r=m;m=p; p=p->next;h->next->next=null; / 使 a1 指向空 h->next=r;/h 指向 An return h; 數據結構隊列、循環隊列鏈隊列 空鏈隊列的判定條件： 定義 Typedef struct ElemType data; struct Qnode *next; Qnode, *QueuePtr;Typedef struct QueuePtr rear; QueuePtr front; LinkQueue;構造一個空鏈隊列 Status InitLinkQueue(LinkQueue &a

24、mp;Q) Q.front=Q.rear=(QueuePtr)malloc(sizeof(Qnode);If(!Q.front) return ERROR; Q.rear->next=null; return OK;插入元素Status EnLinkQueue( LinkQueue &Q, ElemType e) Qnode p; p=(QueuePtr)malloc(sizeof(Qnode); if (!p) return ERROR;p->data=e; p->next=null; Q.rear->next=p;Q.rear=p; return OK;刪除

25、 Q 中隊頭元素，用 e 保存，返回 okStatus DeLinkQueue(LinkQueue &Q, ElemType &e)if(Q.front=Q.rear) return ERROR; / 判斷鏈隊列是否為空 LinkQueue p;p=Q.front->next; / 把 p 放在隊頭元素 e=p->data;Q.front->next=p->next; if(Q.rear=p) Q.rear=Q.front;/如果只有一個元素， rear 和 front 都指向表頭 Free(p);Return OK;循環隊列 判斷循環隊列是否為空或者為

26、滿 設定一個計數器 count Count=0 Count=QueueLength定義(通過一個一維數組實現)#define QueueSize 6 /根據具體 情況設定 Typedef structElemType dataQueueSize;int count;int front;int rear;置隊空Void InitQueue(CirQueue &Q) Q.rear=Q.front=0; /0 代表的是地址 Q.count=0; /0 代表計數器的數值 判斷隊空 /滿Q.count=0;Q.count=QueueSize;e 入隊判斷是否滿隊不滿則：Q.dataQ.rear=

27、e;Q.rear=(Q.rear+1)%Queuesize;Q.count+;出隊判斷是否為空不空則：e=Q.dataQ.front;Q.front=(Q.front+1)%Queuesize;Q.count-;棧和隊列習題 .一個棧的輸入序列為123-n，若輸出序列的第一個元素是n,輸出第i ( K i< n)個元素是()A)不確定B) n-i+1C) iD) n-i答：B若用一個大小為6的數組來實現循環隊列，且當前 rear和front的值分別為0和3，當從隊列中刪除 一個元素，再加入兩個元素后， rear 和 front 的值分別為多少？ ( )A) 1 和 5B) 2和 4C) 4和 2D) 5 和 1【答案】 B【解析】循環隊列是解決假溢出的問題，通常把一維數組看成首尾相接。在循環意義下的加1 運算通常用求模運算來實現。所以入隊和出隊時的操作分別為： rear=(rear+1)%m ， front=(front+1)%m 。假設順序棧的定義為：typedef struct selemtype *base; /* 棧底指針 */sele