數(shù)據(jù)結(jié)構(gòu)_線性表之鏈表實(shí)現(xiàn)_動(dòng)態(tài)存儲(chǔ)結(jié)構(gòu)

1、#include #include #define MAXSIZE 100#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define OVERFLOW -2typedef struct LNode int data; struct LNode *next;LNode;typedef struct LNode *head,*tail; int len;LinkList;LNode *MakeNode(LNode *p,int e)/分配由p指向的值為e的結(jié)點(diǎn),并返回P; 若分配失敗,則返回NULL; if(!(p=(LNode

2、*)malloc(sizeof(LNode) return NULL; p-data=e; p-next=NULL; return p;void FreeNode(LNode *p)/釋放p所指的結(jié)點(diǎn) free(p); p=NULL;int InitList(LinkList *L)/構(gòu)造一個(gè)空的線性鏈表L LNode *p; p=(LNode *)malloc(sizeof(LNode); if(!p) return OVERFLOW; p-next=NULL; L-tail=L-head=p; L-len=0; /printf(%d,L-len); return OK;int ClearL

3、ist(LinkList *L)/將線性鏈表L重置為空表,并釋放原鏈表的結(jié)點(diǎn)空間 if(!L-len) return ERROR; LNode *p,*q; q=L-head-next; p=q; L-head-next=NULL; while(p!=L-tail) p=q-next; FreeNode(q); q=p; /FreeNode(q); L-tail=L-head; L-len=0; return OK;int DestroyList(LinkList *L)/銷毀線性鏈表L,L不再存在 if(!L-len) return ERROR; ClearList(L); FreeNode

4、(L-head); return OK;int InsLast(LinkList *L,LNode *s)/ 將s所指結(jié)點(diǎn)插入在第一個(gè)結(jié)點(diǎn)之前 LNode *h=L-tail; if(!s) /printf(insfirst); return ERROR; h-next=s; L-tail=s; if(h=L-head) L-tail=s; L-len=L-len+1; /printf(ok3); return OK;int DelFirst(LinkList *L,LNode *h,LNode *q)/已知h指向線性鏈表的頭結(jié)點(diǎn),刪除鏈表中的第一個(gè)結(jié)點(diǎn)并以q返回 if(!h-next) re

5、turn ERROR; q=h-next; h-next=q-next; q-next=NULL; if(!h-next) L-tail=h; L-len-; return OK;int Append(LinkList *L,LNode *s)/將指針s所指的一串結(jié)點(diǎn)鏈接在線性鏈表L的最后一個(gè)結(jié)點(diǎn) if(!s) return ERROR; L-tail-next=s; L-len+; while(s-next) s=s-next; L-len+; L-tail=s; return OK;int RemoveLast(LinkList *L,LNode *q)/刪除線性鏈表L中的尾結(jié)點(diǎn)并以q返回

6、,改變鏈表L的尾指針指向新的尾結(jié)點(diǎn) if(!L-len) return ERROR; LNode *p; p=L-head; while( p != L-tail) p=p-next; q=L-tail; p-next=NULL; L-tail=p; L-len-; return OK;int Remove(LinkList *L,int i)/刪除線性鏈表L中的第i個(gè)結(jié)點(diǎn),改變鏈表L的尾指針指向新的尾結(jié)點(diǎn) int j; LNode *q,*p; if(!L-len) return ERROR; if(iL-len) return NULL; p=L-head; for(j=1;jnext;

7、q=p-next; p-next=q-next; L-len-; return OK;LNode *PriorPos(LinkList *L, LNode *p)/已知p指向線性鏈表中的一個(gè)結(jié)點(diǎn)，返回p所指結(jié)點(diǎn)的直接前驅(qū)的位置，若無(wú)前驅(qū)，則返回NULL if(p=L-head-next) return NULL; LNode *q; q=L-head-next; while(q-next!=p) q=q-next; return q;int InsBefore(LinkList *L,LNode *p,LNode *s)/已知p指向線性鏈表L中的一個(gè)結(jié)點(diǎn),將 s 所指結(jié)點(diǎn)插入在 p 所指的結(jié)點(diǎn)

8、之前 if(!s|!p) return ERROR; LNode *q; q=PriorPos(L, p); if(!q) q=L-head; q-next=s; s-next=p; /p=s; L-len+; return OK;int InsAfter(LinkList *L,LNode *p,LNode *s)/ 已知p指向線性鏈表L中的一個(gè)結(jié)點(diǎn),將s所指結(jié)點(diǎn)插入在p所指的結(jié)點(diǎn)之后 if(!s|!p) return ERROR; if(p=L-tail) L-tail=s; s-next=p-next; p-next=s; /p=s; L-len+; return OK;int SetC

9、urElem(LNode *p,int e)/已知p指向線性鏈表中的一個(gè)結(jié)點(diǎn)，用e更新p所指結(jié)點(diǎn)中數(shù)據(jù)元素的值 if( !p ) return ERROR; p-data = e; return OK;int GetCurElem(LNode *p)/已知p指向線性鏈表中的一個(gè)結(jié)點(diǎn)，返回p所指結(jié)點(diǎn)中數(shù)據(jù)元素的值 return p-data;int ListEmpty(LinkList *L)/若線性鏈表為空表，則返回TRUE，否則返回FALSE if(!L-len) return TRUE; else return FALSE;int ListLength(LinkList *L)/返回線性鏈

10、表L中元素個(gè)數(shù) return L-len;LNode *GetHead(LinkList *L)/返回線性鏈表L中頭結(jié)點(diǎn)的位置 return L-head;LNode *GetLast(LinkList *L)/返回線性鏈表L中最后一個(gè)結(jié)點(diǎn)的位置 return L-tail;LNode *NextPos(LinkList *L, LNode *p)/已知p指向線性鏈表中的一個(gè)結(jié)點(diǎn)，返回p所指結(jié)點(diǎn)的直接后繼的位置，若無(wú)后繼則返回NULL if(p=L-tail) return NULL; else return p-next; LNode *LocatePos(LinkList *L,int i

11、,LNode *p)/返回p指示線性鏈表L中第i個(gè)結(jié)點(diǎn)的位置，i 值不合法時(shí)返回NULL int j; if(iL-len) return NULL; p=L-head; for(j=1;jnext; return p;int compare(int a,int b)/比絞兩個(gè)數(shù)的大小 return a-b;LNode *LocateElem(LinkList *L,int e,int(*compare)(int,int)/返回線性鏈表L中第1個(gè)與e滿足函數(shù)compare()判定關(guān)系的元素和位置,若不存在這樣的元素,則返回NULL LNode *p=L-head; do p=p-next; w

12、hile(p&!compare(p-data,e); return p;void visit(int a) printf(%d,a);int ListTraverse(LinkList *L,void (*visit)(int)/依次對(duì)L的每個(gè)元素調(diào)用函數(shù)visit().一旦visit()失敗,則打操作失敗. if(L-len=0) printf(對(duì)不起,線性鏈表為空,無(wú)法輸出!n); else LNode *p=NULL; p=L-head-next; int j; for(j=1;jlen;j+) if(j!=L-len) visit(p-data); printf(-); p=p-nex

13、t; else visit(p-data); printf(n); return OK;void Display(LinkList *L) /輸出鏈表 int i; LNode *p=L-head-next; for(i=1; ilen;i+) printf(%d ,p-data); p=p-next; printf(n);void Input(LinkList *L,LNode *p,LNode *q) int i; char answer; do printf(請(qǐng)輸入整數(shù)：n); scanf(%d,&i); getchar(); p=MakeNode(p,i); InsLast(L,p);

14、 printf(是否繼續(xù)添加結(jié)點(diǎn)（Y/N）n); scanf(%s,&answer); while(answer=y|answer=Y);void Menu() printf( n); printf( 線性鏈表綜合操作 n); printf( n); printf( 1重建空鏈表 n); printf( n); printf( 2添加結(jié)點(diǎn)并輸入數(shù)據(jù) n); printf( n); printf( 3查看全部元素 n); printf( n); printf( 4查找某一結(jié)點(diǎn)值及其前驅(qū)和后繼 n); printf( n); printf( 5在某個(gè)結(jié)點(diǎn)前插入值 n); printf( n); p

15、rintf( 6在某個(gè)結(jié)點(diǎn)后插入值 n); printf( n); printf( 7刪除元素 n); printf( n); printf( 8清除鏈表 n); printf( n); printf( 9退出系統(tǒng) n); printf( n); printf( 請(qǐng)選擇:);void Search(LinkList *L,LNode *p,LNode *q) int n; LNode *p1; printf(親，你想查找第幾個(gè)結(jié)點(diǎn)？n); scanf(%d,&n); p1=LocatePos(L,n,p); if(nL-len) printf(表中查無(wú)此元素n); else printf(鏈表

16、L中第%d個(gè)結(jié)點(diǎn)的值為:%dn,n,p1-data); q=PriorPos(L,p1); if(q) printf(鏈表L中第%d個(gè)結(jié)點(diǎn)的前驅(qū)的值為:%dn,n,q-data); else printf(鏈表L中第%d個(gè)結(jié)點(diǎn)無(wú)前驅(qū)n,n); q=NextPos(L,p1); if(q) printf(鏈表L中第%d個(gè)結(jié)點(diǎn)的后繼的值為:%dn,n,q-data); else printf(鏈表L中第%d個(gè)結(jié)點(diǎn)無(wú)后繼n,n); void InsB(LinkList *L,LNode *p,LNode *q) int n,i; LNode *p1; printf(親，你想第幾個(gè)結(jié)點(diǎn)前添加？n);

17、scanf(%d,&n); p1=LocatePos(L,n,p); if(!p1) printf(表中查無(wú)此元素n); else printf(親，請(qǐng)輸入整數(shù)數(shù)據(jù)n); scanf(%d,&i); q=MakeNode(q,i); InsBefore(L,p1,q); void InsA(LinkList *L,LNode *p,LNode *q) int n,i; LNode *p1; printf(親，你想第幾個(gè)結(jié)點(diǎn)后添加？n); scanf(%d,&n); p1=LocatePos(L,n,p); if(!p1) printf(表中查無(wú)此元素n); else printf(親，請(qǐng)輸入整

18、數(shù)數(shù)據(jù)n); scanf(%d,&i); q=MakeNode(q,i); InsAfter(L,p1,q); void Delete(LinkList *L,LNode *p,LNode *q) int n; LNode *q1; LNode *p1; printf(親，你想刪除第幾個(gè)結(jié)點(diǎn)？n); scanf(%d,&n); if(!L-len) printf(親，鏈表中還木有元素！n); p1=LocatePos(L,n,p); if(!p1) printf(親，刪除失?。); else if(n=L-len) RemoveLast(L,p1); else if(n!=L-len) Remove(L,n); int main() int i,a; LNode *p=NULL,*q=NULL; LinkList La; while(1) Menu(); scanf(%d,&a); switch(a) case 1:if(!InitList(&La) return(OVERFLOW); break; case 2: