數(shù)據(jù)結構C語言版 線性表的單鏈表存儲結構表示和實現(xiàn).doc

#include #include #include /*數(shù)據(jù)結構C語言版 線性表的單鏈表存儲結構表示和實現(xiàn)P28-31 編譯環(huán)境：Dev-C+ 4.9.9.2日期：2011年2月10日 */typedef int ElemType;/ 線性表的單鏈表存儲結構 typedef struct LNodeElemType data;/數(shù)據(jù)域struct LNode *next;/指針域LNode, *LinkList;/ typedef struct LNode *LinkList; / 另一種定義LinkList的方法 / 構造一個空的線性表L int InitList(LinkList *L)/*產(chǎn)生頭結點L,并使L指向此頭結點，頭節(jié)點的數(shù)據(jù)域為空，不放數(shù)據(jù)的。void * malloc(size_t)這里對返回值進行強制類型轉換了，返回值是指向空類型的指針類型。*/(*L) = (LinkList)malloc( sizeof(struct LNode) );if( !(*L) )exit(0);/ 存儲分配失敗(*L)-next = NULL;/ 指針域為空return 1;/ 銷毀線性表L，將包括頭結點在內的所有元素釋放其存儲空間。int DestroyList(LinkList *L) LinkList q;/ 由于單鏈表的每一個元素是單獨分配的，所以要一個一個的進行釋放while( *L )q = (*L)-next;free( *L );/釋放*L = q;return 1;/*將L重置為空表，即將鏈表中除頭結點外的所有元素釋放其存儲空間，但是將頭結點指針域置空，這和銷毀有區(qū)別哦。不改變L，所以不需要用指針。*/int ClearList( LinkList L ) LinkList p, q;p = L-next;/ p指向第一個結點 while( p )/ 沒到表尾則繼續(xù)循環(huán) q = p-next;free( p );/釋放空間p = q;L-next = NULL; / 頭結點指針域為空，鏈表成了一個空表 return 1;/ 若L為空表（根據(jù)頭結點L-next來判斷，為空則是空表），則返回1，/ 否則返回0。int ListEmpty(LinkList L) if( L-next )/ 非空 return 0;elsereturn 1;/ 返回L中數(shù)據(jù)元素個數(shù)。int ListLength(LinkList L) int i = 0;LinkList p = L-next; / p指向第一個結點 while(p) / 沒到表尾，則繼續(xù)循環(huán) i+;p=p-next;return i;/ 算法2.8 P29/ L為帶頭結點的單鏈表的頭指針。當?shù)趇個元素存在時,其值賦給e并/ 返回1,否則返回0。int GetElem(LinkList L,int i,ElemType *e)int j = 1;/ j為計數(shù)器 LinkList p=L-next;/ p指向第一個結點 while(p&jnext;j+; if(!p|ji) / 第i個元素不存在 return 0;*e = p-data; / 取第i個元素 return 1;/ 返回L中第1個與e滿足關系compare()的數(shù)據(jù)元素的位序。/ 若這樣的數(shù)據(jù)元素不存在,則返回值為0int LocateElem(LinkList L,ElemType e,int(*compare)(ElemType,ElemType) int i=0;LinkList p=L-next;while(p)/將鏈表的每一個元素進行對比i+;if(compare(p-data,e) / 找到這樣的數(shù)據(jù)元素 return i;p=p-next;return 0;/ 若cur_e是L的數(shù)據(jù)元素,且不是第一個,則用pre_e返回它的前驅,/ 返回1;否則操作失敗,pre_e無定義,返回-1int PriorElem(LinkList L,ElemType cur_e,ElemType *pre_e) LinkList q, p=L-next;/ p指向第一個結點 while(p-next)/ p所指結點有后繼 q=p-next; / q為p的后繼 if(q-data=cur_e)*pre_e=p-data;return 1;p=q; / p向后移 return -1;/ 若cur_e是L的數(shù)據(jù)元素，且不是最后一個，則用next_e返回它的后繼， / 返回1;否則操作失敗，next_e無定義，返回-1 int NextElem(LinkList L,ElemType cur_e,ElemType *next_e)LinkList p=L-next; / p指向第一個結點 while(p-next) / p所指結點有后繼 if(p-data=cur_e)*next_e=p-next-data;return 1;p=p-next;return -1;/算法2.9 P30/在帶頭結點的單鏈線性表L中第i個位置之前插入元素eint ListInsert(LinkList *L,int i,ElemType e) int j=0;LinkList p=*L,s;while(p & jnext;j+;if(!p | ji-1) / i小于1或者大于表長 return 0;s=(LinkList)malloc(sizeof(struct LNode); / 生成新結點 s-data=e; / 插入L中 s-next=p-next;p-next=s;return 1;/ 算法2.10 P30/ 在帶頭結點的單鏈線性表L中，刪除第i個元素,并由e返回其值int ListDelete(LinkList *L, int i,ElemType *e)int j = 0;LinkList p=*L,q;while(p-next&jnext;j+;if(!p-next|ji-1) / 刪除位置不合理 return 0;q=p-next; / 刪除并釋放結點 p-next=q-next;*e=q-data;free(q);return 1;/ 依次對L的每個數(shù)據(jù)元素調用函數(shù)vi()int ListTraverse(LinkList L,void(*vi)(ElemType)LinkList p=L-next;/對所有元素調用函數(shù)viwhile(p)vi(p-data);p=p-next;printf(n);return 1;/ 在按非降序排列的線性表L中按非降序插入新的數(shù)據(jù)元素e void InsertAscend(LinkList L,ElemType e) LinkList q=L, p=L-next;while(p&ep-data)q=p;p=p-next;q-next=(LinkList)malloc(sizeof(struct LNode); / e插在q后 q-next-data=e;q-next-next=p;/ 按非升序排列的線性表L中按非升序插入新的數(shù)據(jù)元素e void InsertDescend(LinkList L,ElemType e) LinkList q=L,p=L-next;while(p&edata)q=p;p=p-next;q-next=(LinkList)malloc(sizeof(struct LNode); / e插在q后 q-next-data=e;q-next-next=p;/ L的頭部插入新的數(shù)據(jù)元素e,作為鏈表的第一個元素 int HeadInsert(LinkList L,ElemType e)LinkList s;s=(LinkList)malloc(sizeof(struct LNode); / 生成新結點 s-data=e; / 給結點賦值 s-next=L-next; / 插在表頭 L-next=s;return 1;/ 在L的尾部插入新的數(shù)據(jù)元素e,作為鏈表的最后一個元素 int EndInsert(LinkList L,ElemType e) LinkList p=L;while(p-next) / 使p指向表尾元素 p=p-next;p-next=(LinkList)malloc(sizeof(struct LNode); / 在表尾生成新結點 p-next-data=e; / 給新結點賦值 p-next-next=NULL; / 表尾 return 1;/ 刪除L的第一個數(shù)據(jù)元素，并由e返回其值 int DeleteFirst(LinkList L,ElemType *e)LinkList p=L-next;if(p)*e=p-data;L-next=p-next;free(p);return 1;elsereturn 0;/ 刪除L的最后一個數(shù)據(jù)元素，并用e返回其值int DeleteTail(LinkList L,ElemType *e)LinkList p=L,q;if(!p-next) / 鏈表為空 return 0;while(p-next)q=p;p=p-next;q-next=NULL; / 新尾結點的next域設為NULL *e=p-data;free(p);return 1;/ 刪除表中值為e的元素，并返回1；如無此元素，則返回0 int DeleteElem(LinkList L,ElemType e)LinkList p=L,q;while(p)q=p-next;if(q&q-data=e)p-next=q-next;free(q);return 1;p=q;return 0;/ 用e取代表L中第i個元素的值 int ReplaceElem(LinkList L,int i,ElemType e)LinkList p=L;int j=0;/找到第i個元素的位置給pwhile(p-next & jnext;if(j=i)p-data=e;return 1;else / 表中不存在第i個元素 return 0;/ 按非降序建立n個元素的線性表int CreatAscend(LinkList *L,int n) int j;LinkList p,q,s;if(ndata);s-next=NULL;(*L)-next=s;for(j=1;jdata);q=*L;p=(*L)-next;while(p&p-datadata) / p沒到表尾，且所指元素值小于新值 q=p;p=p-next; / 指針后移 s-next=q-next; / 元素插在q的后面 q-next=s;return 1;/ 按非升序建立n個元素的線性表int CreatDescend(LinkList *L,int n) int j;LinkList p,q,s;if(ndata);s-next=NULL;(*L)-next=s;for(j=1;jdata);q=*L;p=(*L)-next;while(p&p-datas-data) / p沒到表尾，且所指元素值大于新值 q=p;p=p-next; / 指針后移 s-next=q-next; / 元素插在q的后面 q-next=s;return 1;/ 返回表頭元素的值int GetFirstElem(LinkList L,ElemType *e) LinkList p=L-next;/第一個結點給pif(!p)/ 空表 return 0;else/ 非空表*e=p-data;return 1;/ 算法2.11 P30 / 逆位序(插在表頭)輸入n個元素的值，建立帶表頭結構的單鏈線性表Lvoid CreateList(LinkList *L,int n)int i;LinkList p;/ 先建立一個帶頭結點的空單鏈表，相當于初始化單鏈表 *L=(LinkList)malloc(sizeof(struct LNode);(*L)-next=NULL; printf(請輸入%d個數(shù)據(jù)n,n);for(i=n;i0;-i)p=(LinkList)malloc(sizeof(struct LNode); / 生成新結點 scanf(%d,&p-data); / 輸入元素值 p-next=(*L)-next; / 插入到表頭 (*L)-next=p;/ 正位序(插在表尾)輸入n個元素的值，建立帶表頭結構的單鏈線性表void CreateList2(LinkList *L,int n) int i;LinkList p,q;/ 先建立一個帶頭結點的空單鏈表，相當于初始化單鏈表 *L=(LinkList)malloc(sizeof(struct LNode); / 生成頭結點 (*L)-next=NULL;q=*L;printf(請輸入%d個數(shù)據(jù)n,n);for(i=1;idata);q-next=p;q=q-next;p-next=NULL;/*用單鏈表重寫 算法2.2 供參考 已知線性表La和Lb中的數(shù)據(jù)元素按值非遞減排列。歸并La和Lb得到新的線性表Lc,Lc的數(shù)據(jù)元素也按值非遞減排列void MergeList(LinkList La,LinkList Lb,LinkList *Lc)int i=1,j=1,k=0;int La_len,Lb_len;ElemType ai,bj;InitList(Lc);La_len=ListLength(La);Lb_len=ListLength(Lb);while(i=La_len&j=Lb_len) / 表La和表Lb均非空GetElem(La,i,&ai);GetElem(Lb,j,&bj);if(ai=bj)ListInsert(Lc,+k,ai);+i;elseListInsert(Lc,+k,bj);+j;while(i=La_len) / 表La非空且表Lb空GetElem(La,i+,&ai);ListInsert(Lc,+k,ai);while(jnext,pb=(*Lb)-next,pc;*Lc=pc=La; / 用La的頭結點作為Lc的頭結點 while(pa&pb)if(pa-data data)pc-next=pa;*Lc=pa;pa=pa-next;elsepc-next=pb;pc=pb;pb=pb-next;pc-next=pa ? pa : pb; / 插入剩余段 free(*Lb); / 釋放Lb的頭結點 Lb=NULL;/ 判斷是否相等的函數(shù)，Union()用到int equal(ElemType c1,ElemType c2) if(c1=c2)return 1;elsereturn 0;/ 算法2.1/ 將所有在線性表Lb中但不在La中的數(shù)據(jù)元素插入到La中 void Union(LinkList La,LinkList Lb) ElemType e;int La_len,Lb_len;int i;La_len=ListLength(La); / 求線性表的長度 Lb_len=ListLength(Lb);for(i=1;i=Lb_len;i+)GetElem(Lb,i,&e); / 取Lb中第i個數(shù)據(jù)元素賦給e if(!LocateElem(La,e,equal) / La中不存在和e相同的元素,則插入之 ListInsert(&La,+La_len,e);/ 數(shù)據(jù)元素判定函數(shù)(相等為1,否則為0) int comp(ElemType c1,ElemType c2)if(c1=c2)return 1;elsereturn 0;void visit(ElemType c)printf(%d ,c);int main()LinkList L, La, Lb, Lc;ElemType e, e0, d;int i, j, n, k;/初始化一個單鏈表i=InitList(&L);/通過插入操作創(chuàng)建一個單鏈表for(j=1;j=5;j+)i=ListInsert(&L,1,j);/調用visit函數(shù)，對單鏈表進行遍歷printf(在L的表頭依次插入15后：L=);ListTraverse(L,visit); / 依次對元素調用visit()，輸出元素的值 /判斷單鏈表是否為空i=ListEmpty(L);printf(L是否空：i=%d(1:是 0:否)n,i);/清空單鏈表i=ClearList(L);printf(清空L后：L=);ListTraverse(L,visit);/判斷單鏈表是否為空i=ListEmpty(L);printf(L是否空：i=%d(1:是 0:否)n,i);/再次通過插入操作創(chuàng)建一個單鏈表for(j=1;j=10;j+)ListInsert(&L,j,j);printf(在L的表尾依次插入110后：L=);ListTraverse(L,visit);/取得單鏈表的第5個元素GetElem(L,5,&e);printf(第5個元素的值為：%dn,e);/在單鏈表中找到和j滿足comp函數(shù)關系的元素for(j=0;j=1;j+)k=LocateElem(L,j,comp);if(k)printf(第%d個元素的值為%dn,k,j);elseprintf(沒有值為%d的元素n,j);/找到某個元素的前驅for(j=1;j=2;j+) / 測試頭兩個數(shù)據(jù) GetElem(L,j,&e0); / 把第j個數(shù)據(jù)賦給e0 i=PriorElem(L,e0,&e); / 求e0的前驅 if(i=-1)printf(元素%d無前驅n,e0);elseprintf(元素%d的前驅為：%dn,e0,e);/找到某個元素的后繼for(j=ListLength(L)-1;j=k;j-)i=ListDelete(&L,j,&e); / 刪除第j個數(shù)據(jù) if(i=0)printf(刪除第%d個數(shù)據(jù)失敗n,j);elseprintf(刪除的元素為：%dn,e);printf(依次輸出L的元素：);ListTraverse(L,visit);/銷毀單鏈表DestroyList(&L);printf(銷毀L后：L=%unn,L);printf(按非降序建立n個元素的線性表L,請輸入元素個數(shù)n: );scanf(%d,&n);CreatAscend(&L,n);printf(依次輸出L的元素：);ListTraverse(L,visit);/ 按非降序插入元素10InsertAscend(L,10); printf(按非降序插入元素10后，線性表L為：);ListTraverse(L,visit);/ 在L的頭部插入12HeadInsert(L,12);/ 在L的尾部插入9 EndInsert(L,9); printf(在L的頭部插入12，尾部插入9后，線性表L為：);ListTraverse(L,visit);i=GetFirstElem(L,&e); printf(第1個元素是: %dn,e); printf(請輸入要刪除的元素的值: );scanf(%d,&e);i=DeleteElem(L,e);if(i)printf(成功刪除%d!n,e);elseprintf(不存在元素%d!n,e);printf(線性表L為：);ListTraverse(L,visit);printf(請輸入要取代的元素的序號 元素的新值: );scanf(%d%d,&n,&e);ReplaceElem(L,n,e);printf(線性表L為：);ListTraverse(L,visit);DestroyList(&L);printf(銷毀L后,按非升序重新建立n個元素的線性表L,請輸入元素個數(shù)n(2): );scanf(%d,&n);CreatDescend(&L,n);printf(依次輸出L的元素：);ListTraverse(L,visit);/ 按非升序插入元素10InsertDescend(L,10);printf(按非升序插入元素10后，線性表L為：);ListTraverse(L,visit);printf(請輸入要刪除的元素的值: );scanf(%d,&e);i=DeleteElem(L,e);if(i)printf(成功刪除%d!n,e);elseprintf(不存在元素%d!n,e);printf(線性表L為：);ListTraverse(L,visit);DeleteFirst(L,&e);DeleteTail(L,&d);printf(刪除表頭元素%d和表尾元素%d后,線性表L為：,e,d);ListTraverse(L,visit);printf(n);/ 測試算法2.11 n = 3;CreateList2(&La,n);/ 正位序輸入n個元素的值 printf(正位創(chuàng)建后La=);/ 輸出鏈表La的內容 ListTraverse(La,visi