一、單鏈表、循環單鏈表、循環雙鏈表各自特點
鏈表是一種常見的基礎數據結構，是一種線性表，但是並不會按線性的順序存儲數據，而是在每個節點裡存到下一個節點的指針。由於不須按順序存儲，鏈表在插入的時候可以達到O(1)的復雜度，比順序表O(logn)快得多，但是查找一個節點或者訪問特定編號的節點則需要O(n)的時間，而順序表的時間復雜度是O(1)。
鏈表結構可以充分利用計算機內存空間，實現靈活的內存動態管理。但是鏈表失去了數組隨機讀取的優點，同時鏈表由於增加了結點的指針域，空間開銷比較大。
鏈表由一連串節點組成，每個節點包含任意的實例數據(data fields)和一或兩個用來指向明上一個/或下一個節點的位置的鏈接"links"）。鏈表是一種自我指示數據類型，因為它包含指向另一個相同類型的數據的指針。鏈表允許插入和移除表上任意位置上的節點，但是不允許隨機存取。鏈表有很多種不同的類型：單向鏈表，雙向鏈表以及循環鏈表。
鏈表可以在多種編程語言中實現。
1、單向鏈表或者單鏈表
單向鏈表，它包含兩個域，一個信息域和一個指針域。這個鏈接指向表中的下一個節點，而最後一個節點則指向一個空值NULL。
單向鏈表只可向一個方向遍歷。
查找一個節點的時候需要從第一個節點開始每次訪問下一個節點，一直訪問到需要的位置。也可以提前把一個節點的位置另外保存起來，然後直接訪問。
2、 雙向鏈表,也叫雙鏈表
雙向鏈表中不僅有指向後一個節點的指針，還有指向前一個節點的指針。第一個節點的"前連接"指向NULL，最後一個節點的"後連接"指向NULL。
這樣可以從任何一個節點訪問前一個節點，也可以訪問後一個節點，以至整個鏈表。一般是在需要大批量的另外儲存數據在鏈表中的位置的時候用。
由於另外儲存了指向鏈表內容的指針，並且可能會修改相鄰的節點，有的時候第一個節點可能會被刪除或者在之前添加一個新的節點。這時候就要修改指向首個節點的指針。
有一種方便的可以消除這種特殊情況的方法是在最後一個節點之後、第一個節點之前儲存一個永遠不會被刪除或者移動的虛擬節點，形成一個循環鏈表。這個虛擬節點之後的節點就是真正的第一個節點。這種情況通常可以用這個虛擬節點直接表示這個鏈表。
3、 循環鏈表
在一個循環鏈表中, 首節點和末節點被連接在一起。這種方式在單向和雙向鏈表中皆可實現。要轉換一個循環鏈表，你開始於任意一個節點然後沿著列表的任一方向直到返回開始的節點。循環鏈表可以被視為"無頭無尾"。
循環鏈表中第一個節點之前就是最後一個節點，反之亦然。循環鏈表的無邊界使得在這樣的鏈表上設計算法會比普通鏈表更加容易。對於新加入的節點應該是在第一個節點之前還是最後一個節點之後可以根據實際要求靈活處理，區別不大。
另外有一種模擬的循環鏈表，就是在訪問到最後一個節點之後的時候，手工跳轉到第一個節點。訪問到第一個節點之前的時候也一樣。這樣也可以實現循環鏈表的功能，在直接用循環鏈表比較麻煩或者可能會出現問題的時候可以用。
鏈表中的節點不需要以特定的方式存儲，但是集中存儲也是可以的，主要分下面這幾種具體的存儲方法：
共用存儲空間：鏈表的節點和其它的數據共用存儲空間，優點是可以存儲無限多的內容不過要處理器支持這個大小，並且存儲空間足夠的情況下），不需要提前分配內存,存儲一個申請一個，如C語言的MALLOC；缺點是由於內容分散，有時候可能不方便調試。
獨立存儲空間：一個鏈表或者多個鏈表使用獨立的存儲空間，一般用數組或者類似結構實現，優點是可以自動獲得一個附加數據：唯一的編號/索引，並且方便調試；缺點是不能動態的分配內存。當然，另外的在上面加一層塊狀鏈表用來分配內存也是可以的，這樣就解決了這個問題。這種方法叫做數組模擬鏈表，但是事實上只是用表示在數組中的位置的下標索引代替了指向內存地址的指針，這種下標索引其實也是邏輯上的指針，整個結構還是鏈表，並不算是被模擬的但是可以說成是用數組實現的鏈表）。
鏈表用來構建許多其它數據結構，如堆棧，行列和他們的衍生。
節點的數據域也可以成為另一個鏈表。通過這種手段，我們可以用列表來構建許多鏈性數據結構；這個實例產生於Lisp編程語言，在Lisp中鏈表是初級數據結構，並且現在成為了常見的基礎編程模式。 有時候，鏈表用來生成聯合數組，在這種情況下我們稱之為聯合數列。這種情況下用鏈表會優於其它數據結構，如自平對分查找樹self-balancing binary search trees）甚至是一些小的數據集合。不管怎樣，一些時候一個鏈表在這樣一個樹中建立一個節點子集，並且以此來更有效率地轉換這個集合。
二、 順序表、單鏈表、雙鏈表、有序單鏈表 算法與實現
1、順序表的實現
#include <stdio.h>
#include <malloc.h>
#define MaxSize 50
typedef char ElemType;
typedef struct
{
ElemType data[MaxSize];
int length;
}SqList;
void InitList(SqList *&L)
{
L = (SqList *)malloc(sizeof(SqList));
L->length = 0;
}
void DestroyList(SqList *L)
{
free(L);
}
int ListEmpty(SqList *L)
{
return(L->length==0);
}
int ListLength(SqList *L)
{
return(L->length);
}
void DispList(SqList *L)
{
int i;
if (ListEmpty(L))
{
return ;
}
for(i = 0;i < L->length;i++)
{
printf("%c",L->data[i]);
}
printf("\n");
}
int GetElem(SqList *L,int i,ElemType &e)
{
if (i<1||i>L->length)
{
return 0;
}
e = L->data[i-1];
return 1;
}
int LocateElem(SqList *L, ElemType e)
{
int i = 0;
while(i<L->length&&L->data[i]!=e)
i++;
if (i>L->length)
{
return 0 ;
}
else
{
return i+1;
}
}
int ListInsert(SqList *&L,int i,ElemType e)
{
int j;
if (i<1||i>L->length+1)
{
return 0;
}
i--;
for (j = L->length;j>i;j--)
{
L->data[j]=L->data[j-1];
}
L->data[i] = e;
L->length++;
return 1;
}
int ListDelete(SqList *&L,int i,ElemType &e)
{
int j;
if (i<1||i>L->length)
{
return 0;
}
i--;
e = L->data[i];
for (j = i;j<L->length-1;j++)
{
L->data[j] = L->data[j+1];
}
L->length--;
return 1;
}
int main()
{
SqList *L;
ElemType e;
printf("初始化順序表L\n");
InitList(L);
printf("依次采用尾插法插入a,b,c,d,e元素\n");
ListInsert(L,1,'a');
ListInsert(L,2,'b');
ListInsert(L,3,'c');
ListInsert(L,4,'d');
ListInsert(L,5,'e');
printf("輸出順序表L:");
DispList(L);
printf("順序表L長度=%d\n",ListLength(L));
printf("順序表L為%s\n",(ListEmpty(L)?"空":"非空"));
GetElem(L,3,e);
printf("順序表L的第3個元素=%c\n",e);
printf("在第四個元素位置上插入f元素\n");
ListInsert(L,4,'f');
printf("輸出順序表L:");
DispList(L);
printf("刪除L的第3個元素\n");
ListDelete(L,3,e);
printf("輸出順序表L:");
DispList(L);
printf("釋放順序表L\n");
DestroyList(L);
return 0;
}
2、單鏈表的實現
#include <stdio.h>
#include <malloc.h>
typedef char ElemType;
typedef struct LNode
{
ElemType data;
struct LNode *next;
}LinkList;
void InitList(LinkList *&L)
{
L = (LinkList *)malloc(sizeof(LinkList));
L->next = NULL;
}
void DestroyList(LinkList *&L)
{
LinkList *p = L,*q = p->next;
while(q!=NULL)
{
free(p);
p = q;
q = p->next;
}
free(p);
}
int ListEmpty(LinkList *L)
{
return(L->next==NULL);
}
int ListLength(LinkList *L)
{
LinkList *p = L;
int i = 0;
while(p->next!=NULL)
{
i++;
p = p->next;
}
return(i);
}
void DispList(LinkList *L)
{
LinkList *p = L->next;
while(p!=NULL)
{
printf("%c",p->data);
p = p->next;
}
printf("\n");
}
int GetElem(LinkList *L,int i,ElemType &e)
{
int j = 0;
LinkList *p = L;
while(j<i&&p!=NULL)
{
j++;
p = p->next;
}
if (p == NULL)
{
return 0 ;
}
else
{
e = p->data;
return 1;
}
}
int LocateElem(LinkList *L,ElemType e)
{
LinkList *p = L->next;
int n = 1;
while (p!=NULL&&p->data!=e)
{
p = p->next;
n++;
}
if (p == NULL)
{
return(0);
}
else
{
return(n);
}
}
int ListInsert(LinkList *&L,int i,ElemType e)
{
int j = 0;
LinkList *p = L,*s;
while(j<i-1&&p!=NULL)
{
j++;
p = p->next;
}
if (p == NULL)
{
return 0;
}
else
{
s = (LinkList *)malloc(sizeof(LinkList));
s->data = e;
s->next = p->next;
p->next = s;
return 1;
}
}
int ListDelete(LinkList *&L,int i,ElemType &e)
{
int j = 0;
LinkList *p = L,*q;
while (j<i-1&&p!=NULL)
{
j++;
p = p->next;
}
if (p == NULL)
{
return 0;
}
else
{
q = p->next;
if (q == NULL)
return 0;
e = q->data;
p->next = q->next;
free(q);
return 1;
}
}
int main()
{
LinkList *h;
ElemType e;
printf("(1)初始化單鏈表h\n");
InitList(h);
printf("(2)依次采用尾插法插入a,b,c,d,e元素\n");
ListInsert(h,1,'a');
ListInsert(h,2,'b');
ListInsert(h,3,'c');
ListInsert(h,4,'d');
ListInsert(h,5,'e');
printf("(3)輸出單鏈表h:");
DispList(h);
printf("(4)單鏈表h長度=%d\n",ListLength(h));
printf("(5)單鏈表h為%s\n",(ListEmpty(h)?"空":"非空"));
GetElem(h,3,e);
printf("(6)單鏈表h的第3個元素=%c\n",e);
printf("(7)元素a的位置=%d\n",LocateElem(h,'a'));
printf("(8)在第4個元素位置上插入f元素\n");
ListInsert(h,4,'f');
printf("(9)輸出單鏈表h:");
DispList(h);
printf("(10)刪除h的第3個元素\n");
ListDelete(h,3,e);
printf("(11)輸出單鏈表h:");
DispList(h);
printf("(12)釋放單鏈表h\n");
DestroyList(h);
}
3、雙鏈表的實現
#include <stdio.h>
#include <malloc.h>
typedef char ElemType;
typedef struct DNode
{
ElemType data;
struct DNode *prior;
struct DNode *next;
}DLinkList;
void InitList(DLinkList *&L)
{
L = (DLinkList *)malloc(sizeof(DLinkList));
L->prior = L->next = NULL;
}
void DestroyList(DLinkList *&L)
{
DLinkList *p = L,*q = p->next;
while(q!=NULL)
{
free(p);
p = q;
q = p->next;
}
free(p);
}
int ListEmpty(DLinkList *L)
{
return(L->next == NULL);
}
int ListLength(DLinkList *L)
{
DLinkList *p = L;
int i = 0;
while(p->next!=NULL)
{
i++;
p = p->next;
}
return(i);
}
void DispList(DLinkList *L)
{
DLinkList *p = L->next;
while (p!=NULL)
{
printf("%c",p->data);
p= p->next;
}
printf("\n");
}
int GetElem(DLinkList *L,int i,ElemType &e)
{
int j = 0;
DLinkList *p = L;
while (j<i&&p!=NULL)
{
j++;
p = p->next;
}
if (p == NULL)
{
return 0;
}
else
{
e = p->data;
return 1;
}
}
int LocateElem(DLinkList *L,ElemType e)
{
int n = 1;
DLinkList *p = L->next;
while(p!=NULL&&p->data!=e)
{
n++;
p= p->next;
}
if (p==NULL)
{
return(0);
}
else
return(n);
}
int ListInsert(DLinkList *&L,int i,ElemType e)
{
int j = 0;
DLinkList *p = L,*s;
while (j<i-1&&p!=NULL)
{
j++;
p = p->next;
}
if (p == NULL)
{
return 0;
}
else
{
s = (DLinkList *)malloc(sizeof(DLinkList));
s->data = e;
s->next = p->next;
if (p->next!=NULL)
{
p->next->prior = s;
}
s->prior = p;
p->next = s;
return 1;
}
}
int ListDelete(DLinkList *&L,int i,ElemType &e)
{
int j = 0;
DLinkList *p = L,*q;
while(j<i-1&&p!=NULL)
{
j++;
p = p->next;
}
if (p == NULL)
{
return 0;
}
else
{
q = p->next;
if (q == NULL)
{
return 0;
}
e = q->data;
p->next = q->next;
if (p->next!=NULL)
{
p->next->prior = p;
}
free(q);
return 1;
}
}
void main()
{
DLinkList *h;
ElemType e;
printf("(1)初始化雙鏈表h\n");
InitList(h);
printf("(2)依次采用尾插法插入a,b,c,d,e元素\n");
ListInsert(h,1,'a');
ListInsert(h,2,'b');
ListInsert(h,3,'c');
ListInsert(h,4,'d');
ListInsert(h,5,'e');
printf("(3)輸出雙鏈表h:");
DispList(h);
printf("(4)雙鏈表h長度=%d\n",ListLength(h));
printf("(5)雙鏈表h為%s\n",(ListEmpty(h)?"空":"非空"));
GetElem(h,3,e);
printf("(6)雙鏈表h的第3個元素=%c\n",e);
printf("(7)元素a的位置=%d\n",LocateElem(h,'a'));
printf("(8)在第4個元素位置上插入f元素\n");
ListInsert(h,4,'f');
printf("(9)輸出雙鏈表h:");
DispList(h);
printf("(10)刪除h的第3個元素\n");
ListDelete(h,3,e);
printf("(11)輸出雙鏈表h:");
DispList(h);
printf("(12)釋放雙鏈表h\n");
DestroyList(h);
}
4、循環單鏈表的實現
#include <stdio.h>
#include <malloc.h>
typedef char ElemType;
typedef struct LNode//定義單鏈表結點類型
{
ElemType data;
struct LNode *next;
} LinkList;
void InitList(LinkList *&L)
{
L=(LinkList *)malloc(sizeof(LinkList));//創建頭結點
L->next=L;
}
void DestroyList(LinkList *&L)
{
LinkList *p=L,*q=p->next;
while (q!=L)
{
free(p);
p=q;
q=p->next;
}
free(p);
}
int ListEmpty(LinkList *L)
{
return(L->next==L);
}
int ListLength(LinkList *L)
{
LinkList *p=L;int i=0;
while (p->next!=L)
{
i++;
p=p->next;
}
return(i);
}
void DispList(LinkList *L)
{
LinkList *p=L->next;
while (p!=L)
{
printf("%c",p->data);
p=p->next;
}
printf("\n");
}
int GetElem(LinkList *L,int i,ElemType &e)
{
int j=0;
LinkList *p;
if (L->next!=L)//單鏈表不為空表時
{
if (i==1)
{
e=L->next->data;
return 1;
}
else//i不為1時
{
p=L->next;
while (j<i-1 && p!=L)
{
j++;
p=p->next;
}
if (p==L)
return 0;
else
{
e=p->data;
return 1;
}
}
}
else//單鏈表為空表時
return 0;
}
int LocateElem(LinkList *L,ElemType e)
{
LinkList *p=L->next;
int n=1;
while (p!=L && p->data!=e)
{
p=p->next;
n++;
}
if (p==L)
return(0);
else
return(n);
}
int ListInsert(LinkList *&L,int i,ElemType e)
{
int j=0;
LinkList *p=L,*s;
if (p->next==L || i==1)//原單鏈表為空表或i==1時
{
s=(LinkList *)malloc(sizeof(LinkList));//創建新結點*s
s->data=e;
s->next=p->next;//將*s插入到*p之後
p->next=s;
return 1;
}
else
{
p=L->next;
while (j<i-2 && p!=L)
{
j++;
p=p->next;
}
if (p==L)//未找到第i-1個結點
return 0;
else//找到第i-1個結點*p
{
s=(LinkList *)malloc(sizeof(LinkList));//創建新結點*s
s->data=e;
s->next=p->next;//將*s插入到*p之後
p->next=s;
return 1;
}
}
}
int ListDelete(LinkList *&L,int i,ElemType &e)
{
int j=0;
LinkList *p=L,*q;
if (p->next!=L)//原單鏈表不為空表時
{
if (i==1)//i==1時
{
q=L->next;//刪除第1個結點
e=q->data;
L->next=q->next;
free(q);
return 1;
}
else//i不為1時
{
p=L->next;
while (j<i-2 && p!=L)
{
j++;
p=p->next;
}
if (p==L)//未找到第i-1個結點
return 0;
else//找到第i-1個結點*p
{
q=p->next;//q指向要刪除的結點
e=q->data;
p->next=q->next;//從單鏈表中刪除*q結點
free(q);//釋放*q結點
return 1;
}
}
}
else return 0;
}
void main()
{
LinkList *h;
ElemType e;
printf("(1)初始化循環單鏈表h\n");
InitList(h);
printf("(2)依次采用尾插法插入a,b,c,d,e元素\n");
ListInsert(h,1,'a');
ListInsert(h,2,'b');
ListInsert(h,3,'c');
ListInsert(h,4,'d');
ListInsert(h,5,'e');
printf("(3)輸出循環單鏈表h:");
DispList(h);
printf("(4)循環單鏈表h長度=%d\n",ListLength(h));
printf("(5)循環單鏈表h為%s\n",(ListEmpty(h)?"空":"非空"));
GetElem(h,3,e);
printf("(6)循環單鏈表h的第3個元素=%c\n",e);
printf("(7)元素a的位置=%d\n",LocateElem(h,'a'));
printf("(8)在第4個元素位置上插入f元素\n");
ListInsert(h,4,'f');
printf("(9)輸出循環單鏈表h:");
DispList(h);
printf("(10)刪除h的第3個元素\n");
ListDelete(h,3,e);
printf("(11)輸出循環單鏈表h:");
DispList(h);
printf("(12)釋放循環單鏈表h\n");
DestroyList(h);
}
5、循環雙鏈表的實現
#include <stdio.h>
#include <malloc.h>
typedef char ElemType;
typedef struct DNode//定義雙鏈表結點類型
{
ElemType data;
struct DNode *prior;//指向前驅結點
struct DNode *next;//指向後繼結點
} DLinkList;
void InitList(DLinkList *&L)
{
L=(DLinkList *)malloc(sizeof(DLinkList)); //創建頭結點
L->prior=L->next=L;
}
void DestroyList(DLinkList *&L)
{
DLinkList *p=L,*q=p->next;
while (q!=L)
{
free(p);
p=q;
q=p->next;
}
free(p);
}
int ListEmpty(DLinkList *L)
{
return(L->next==L);
}
int ListLength(DLinkList *L)
{
DLinkList *p=L;int i=0;
while (p->next!=L)
{
i++;
p=p->next;
}
return(i);
}
void DispList(DLinkList *L)
{
DLinkList *p=L->next;
while (p!=L)
{
printf("%c",p->data);
p=p->next;
}
printf("\n");
}
int GetElem(DLinkList *L,int i,ElemType &e)
{
int j=0;
DLinkList *p;
if (L->next!=L)//雙鏈表不為空表時
{
if (i==1)
{
e=L->next->data;
return 1;
}
else//i不為1時
{
p=L->next;
while (j<i-1 && p!=L)
{
j++;
p=p->next;
}
if (p==L)
return 0;
else
{
e=p->data;
return 1;
}
}
}
else//雙鏈表為空表時
return 0;
}
int LocateElem(DLinkList *L,ElemType e)
{
int n=1;
DLinkList *p=L->next;
while (p!=NULL && p->data!=e)
{
n++;
p=p->next;
}
if (p==NULL)
return(0);
else
return(n);
}
int ListInsert(DLinkList *&L,int i,ElemType e)
{
int j=0;
DLinkList *p=L,*s;
if (p->next==L)//原雙鏈表為空表時
{
s=(DLinkList *)malloc(sizeof(DLinkList));//創建新結點*s
s->data=e;
p->next=s;s->next=p;
p->prior=s;s->prior=p;
return 1;
}
else if (i==1)//原雙鏈表不為空表但i=1時
{
s=(DLinkList *)malloc(sizeof(DLinkList));//創建新結點*s
s->data=e;
s->next=p->next;p->next=s;//將*s插入到*p之後
s->next->prior=s;s->prior=p;
return 1;
}
else
{
p=L->next;
while (j<i-2 && p!=L)
{j++;
p=p->next;
}
if (p==L)//未找到第i-1個結點
return 0;
else//找到第i-1個結點*p
{
s=(DLinkList *)malloc(sizeof(DLinkList));//創建新結點*s
s->data=e;
s->next=p->next;//將*s插入到*p之後
if (p->next!=NULL) p->next->prior=s;
s->prior=p;
p->next=s;
return 1;
}
}
}
int ListDelete(DLinkList *&L,int i,ElemType &e)
{
int j=0;
DLinkList *p=L,*q;
if (p->next!=L)//原雙鏈表不為空表時
{
if (i==1)//i==1時
{
q=L->next;//刪除第1個結點
e=q->data;
L->next=q->next;
q->next->prior=L;
free(q);
return 1;
}
else//i不為1時
{
p=L->next;
while (j<i-2 && p!=NULL)
{
j++;
p=p->next;
}
if (p==NULL)//未找到第i-1個結點
return 0;
else//找到第i-1個結點*p
{
q=p->next;//q指向要刪除的結點
if (q==NULL) return 0;//不存在第i個結點
e=q->data;
p->next=q->next;//從單鏈表中刪除*q結點
if (p->next!=NULL) p->next->prior=p;
free(q);//釋放*q結點
return 1;
}
}
}
else return 0;//原雙鏈表為空表時
}
void main()
{
DLinkList *h;
ElemType e;
printf("(1)初始化循環雙鏈表h\n");
InitList(h);
printf("(2)依次采用尾插法插入a,b,c,d,e元素\n");
ListInsert(h,1,'a');
ListInsert(h,2,'b');
ListInsert(h,3,'c');
ListInsert(h,4,'d');
ListInsert(h,5,'e');
printf("(3)輸出循環雙鏈表h:");
DispList(h);
printf("(4)循環雙鏈表h長度=%d\n",ListLength(h));
printf("(5)循環雙鏈表h為%s\n",(ListEmpty(h)?"空":"非空"));
GetElem(h,3,e);
printf("(6)循環雙鏈表h的第3個元素=%c\n",e);
printf("(7)元素a的位置=%d\n",LocateElem(h,'a'));
printf("(8)在第4個元素位置上插入f元素\n");
ListInsert(h,4,'f');
printf("(9)輸出循環雙鏈表h:");
DispList(h);
printf("(10)刪除h的第3個元素\n");
ListDelete(h,3,e);
printf("(11)輸出循環雙鏈表h:");
DispList(h);
printf("(12)釋放循環雙鏈表h\n");
DestroyList(h);
}
6、有序單鏈表的和、交、並、差實現
#include <stdio.h>
#include <malloc.h>
typedef char ElemType;
typedef struct LNode//定義單鏈表結點類型
{
ElemType data;
struct LNode *next;
} LinkList;
void DispList(LinkList *L)
{
LinkList *p=L->next;
while (p!=NULL)
{
printf("%c",p->data);
p=p->next;
}
printf("\n");
}
void CreateListR(LinkList *&L,ElemType a[],int n) //尾插法建表
{
LinkList *s,*r;int i;
L=(LinkList *)malloc(sizeof(LinkList));//創建頭結點
L->next=NULL;
r=L;//r始終指向終端結點,開始時指向頭結點
for (i=0;i<n;i++)
{
s=(LinkList *)malloc(sizeof(LinkList));//創建新結點
s->data=a[i];
r->next=s;//將*s插入*r之後
r=s;
}
r->next=NULL;//終端結點next域置為NULL
}
void Sort(LinkList *&head)//單鏈表元素排序
{
LinkList *p=head->next,*q,*r;
if (p!=NULL)//若原單鏈表中有一個或以上的數據結點
{
r=p->next;//r保存*p結點後繼結點的指針
p->next=NULL;//構造只含一個數據結點的有序表
p=r;
while (p!=NULL)
{
r=p->next;//r保存*p結點後繼結點的指針
q=head;
while (q->next!=NULL && q->next->data<p->data)//在有序表中找插入*p的前驅結點*q
q=q->next;
p->next=q->next;//將*p插入到*q之後
q->next=p;
p=r;
}
}
}
void Union(LinkList *ha,LinkList *hb,LinkList *&hc) //求兩有序集合的並
{
LinkList *pa=ha->next,*pb=hb->next,*s,*tc;
hc=(LinkList *)malloc(sizeof(LinkList));//創建頭結點
tc=hc;
while (pa!=NULL && pb!=NULL)
{
if (pa->data<pb->data)
{
s=(LinkList *)malloc(sizeof(LinkList));//復制結點
s->data=pa->data;
tc->next=s;tc=s;
pa=pa->next;
}
else if (pa->data>pb->data)
{
s=(LinkList *)malloc(sizeof(LinkList));//復制結點
s->data=pb->data;
tc->next=s;tc=s;
pb=pb->next;
}
else
{
s=(LinkList *)malloc(sizeof(LinkList));//復制結點
s->data=pa->data;
tc->next=s;tc=s;
pa=pa->next;//重復的元素只復制一個
pb=pb->next;
}
}
if (pb!=NULL) pa=pb;//復制余下的結點
while (pa!=NULL)
{
s=(LinkList *)malloc(sizeof(LinkList));//復制結點
s->data=pa->data;
tc->next=s;tc=s;
pa=pa->next;
}
tc->next=NULL;
}
void InterSect(LinkList *ha,LinkList *hb,LinkList *&hc)//求兩有序集合的差
{
LinkList *pa=ha->next,*pb,*s,*tc;
hc=(LinkList *)malloc(sizeof(LinkList));
tc=hc;
while (pa!=NULL)
{
pb=hb->next;
while (pb!=NULL && pb->data<pa->data)
pb=pb->next;
if (pb!=NULL && pb->data==pa->data)//若pa結點值在B中
{
s=(LinkList *)malloc(sizeof(LinkList));//復制結點
s->data=pa->data;
tc->next=s;tc=s;
}
pa=pa->next;
}
tc->next=NULL;
}
void Subs(LinkList *ha,LinkList *hb,LinkList *&hc)//求兩有序集合的差
{
LinkList *pa=ha->next,*pb,*s,*tc;
hc=(LinkList *)malloc(sizeof(LinkList));
tc=hc;
while (pa!=NULL)
{
pb=hb->next;
while (pb!=NULL && pb->data<pa->data)
pb=pb->next;
if (!(pb!=NULL && pb->data==pa->data))//若pa結點值不在B中
{
s=(LinkList *)malloc(sizeof(LinkList));//復制結點
s->data=pa->data;
tc->next=s;tc=s;
}
pa=pa->next;
}
tc->next=NULL;
}
void main()
{
LinkList *ha,*hb,*hc;
ElemType a[]={'c','a','e','h'};
ElemType b[]={'f','h','b','g','d','a'};
CreateListR(ha,a,4);
CreateListR(hb,b,6);
printf("原 集 合A:");DispList(ha);
printf("原 集 合B:");DispList(hb);
Sort(ha);
Sort(hb);
printf("有序集合A:");DispList(ha);
printf("有序集合B:");DispList(hb);
Union(ha,hb,hc);
printf("集合的並C:");DispList(hc);
InterSect(ha,hb,hc);
printf("集合的交C:");DispList(hc);
Subs(ha,hb,hc);
printf("集合的差C:");DispList(hc);
}
