單鏈表逆置，單鏈
單鏈表在數據結構中算是一個十分基礎的結構。在單鏈表上可以有很多的其他衍生比如，循環鏈表，帶頭結點的單鏈表，雙向鏈表等等。同時單鏈表在實際應用中也很有很重要的意義。舉例說明：集合的交集、並集問題，使用循環鏈表可以解決約瑟夫環問題、使用鏈表可以解決多項式的加法乘法。
也許在以後的學習中很少自己再完整寫過鏈表，但是在數據結構這門課的學習中，將一些基礎的鏈表操作寫一遍是很重要的。
單鏈表的一些優點：相對於順序表而言，插入刪除算法較簡便，但是對於查找以及返回某位置的數據卻沒有順序表方便。
下面代碼給出單鏈表的結構定義，以及簡單的逆序操作。
代碼：
1 #include<bits/stdc++.h>
2
3 #define max_size 1000010
4 int a[max_size];
5
6 using namespace std;
7
8 typedef int DataType;//類型定義
9 typedef struct node //單鏈表
10 {
11 DataType data;
12 struct node* next;
13 } LinkedNode,*LinkList;
14
15 /****由數組創建單鏈表****/
16 LinkList CreateList(DataType a[],int n)
17 {
18 LinkedNode* ListHead=new LinkedNode();
19 ListHead->data=a[0];
20 ListHead->next=NULL;
21 for(int i=n-1; i>=1; i--)
22 {
23 LinkedNode* p=new LinkedNode();
24 p->data=a[i];
25 p->next=ListHead->next;
26 ListHead->next=p;
27 }
28 return ListHead;
29 }
30
31 void PrintList(LinkList ListHead)
32 {
33 if(NULL==ListHead)cout<<"The List is empty!"<<endl;
34 else
35 {
36 LinkedNode* p=ListHead;
37 while(p!=NULL)
38 {
39 cout<<p->data<<" ";
40 p=p->next;
41 }
42 cout<<endl;
43 }
44 }
45
46 void ReverseList(LinkedNode* pCur,LinkList& ListHead)//遞歸算法
47 {
48 if( (NULL==pCur)||(NULL==pCur->next) )
49 {
50 ListHead=pCur;
51 }
52 else
53 {
54 LinkedNode* pNext=pCur->next;
55 ReverseList(pNext,ListHead); //遞歸逆置後繼結點
56 pNext->next=pCur; //將後繼結點指向當前結點。
57 pCur->next=NULL;
58 }
59 }
60
61 int main()
62 {
63
64 while(true)
65 {
66 int n;
67 cout<<"請輸入創建單鏈表的長度:"<<endl;
68 cin>>n;
69 for(int i=0; i<n; i++)
70 {
71 cout<<"請輸入第"<<i+1<<"個數據:";
72 cin>>a[i];
73 }
74 LinkedNode* list=CreateList(a,n);
75 cout<<"逆置前:"<<endl;
76 PrintList(list);
77 LinkedNode*pTemp=list;
78 ReverseList(pTemp,list);
79 cout<<"逆置後:"<<endl;
80 PrintList(list);
81 }
82 return 0;
83 }
下面給出其他操作的代碼：
單鏈表結構定義：
1 //程序2-15（單鏈表的結構定義）
2
3 typedef int DataType;
4 typedef struct node//鏈表結點
5 {
6 DataType data;//數據域
7 struct node *link;//鏈接指針域
8 }LinkNode, *LinkList;
9
10 //單鏈表適用於插入或刪除頻繁、存儲空間需求不定的情形
11
12 /* （1）單鏈表中數據的邏輯結構與其物理結構可能不一致，
13 通過指針將各個元素按照線性表的邏輯順序連接起來
14 （2）單鏈表的長度可以擴充
15 （3）對單鏈表的便利和查找只能從頭指針指示的首元節點開始，
16 不能像順序表那樣直接訪問某個指定的節點
17 （4）當進行插入或刪除運算時，只需修改相關結點的指針域即可，既方便又快捷
18 （5）由於單鏈表的每個結點帶有指針域，因而比順序表需要的存儲空間多
19 */
單鏈表的插入算法：
![]()
1 //程序2-16（單鏈表插入算法）
2
3 int Insert(LinkList& first,int i,DataType x)//將新元素x插入到第i個節點的位置。
4 //i從1開始，i=1,表示插入到原首結點之前
5 {
6 if(!first||i==1)//插入到空表或非空表的首元結點
7 {
8 LinkNode *newnode=new LinkNode;//建立新的結點
9 if(!newnode){cerr<<"存儲分配錯誤!\n";exit(1);}
10 newnode->data=x;
11 newnode->link=first;first=newnode;//新結點成為第一個結點
12 }
13 else//插入到鏈中或鏈尾
14 {
15 LinkNode *p=first;//為了找到第i-1個結點，需要新建一個指針來找到第i-1個結點
16 int k=1;
17 while(P!=NULL&&k<i-1)
18 {
19 p=p->link;
20 k++;
21 }//利用循環將p指向第i-1個結點的位置
22 if(p==NULL&&first)
23 {cerr<<"無效的插入位置!\n";return 0;}//判斷是否合理，如果表為空或者表太短則返回0
24 else//接下來就開始插入
25 {
26 LinkNode *newnode=new LinkNode;//建立一個新結點
27 if(!newNode){cerr<<"存儲分配錯誤!\n";exit(1);}
28 newnode->data=x;
29 newnode->link=p->link;
30 p->link=newnode;
31 }
32 }
33 return 1;
34 };
View Code
單鏈表的刪除算法：
![]()
1 //程序2-17（單鏈表的刪除算法）
2
3 int Remove(LinkList &first,int i,DataType &x)//將單鏈表的第i個元素刪去，i從1開始，
4 // 引用型參數x返回被刪元素的值
5 {
6 LinkNode *q,*p;//p來表示第i-1個結點的位置,q來表示要刪除的結點
7 int k;
8 if(i<=1){q=first,first=first->link;}//刪除首結點
9 else//刪除鏈表中部或尾部結點
10 {
11 p=first;
12 k=1;
13 while(p!=NULL&&k<i-1)//找到第i-1個節點的位置
14 {
15 p=p->link;
16 k++;
17 }
18 if(p==NULL||p->link==NULL)//如果表太短或表為空 則返回0
19 {cerr<<"無效的刪除位置!\n";return 0;}
20 q=p->link;//保存第i個結點
21 p->link=q->link;//將第i-1個結點和第i+1個結點鏈接
22 }
23 x=q->data;//取出被刪結點的數據值
24 delete q;//刪除結點
25 return 1
26 }
View Code
單鏈表的一些其他操作（初始化、表空、清空、表長計算等）：
![]()
1 //程序2-18（單鏈表部分常用操作的實現）
2 //帶頭結點的單鏈表
3 void initList(LinkList &first)//初始化單鏈表
4 {
5 first=new LinkNode;
6 if(!first){cerr<<"存儲分配錯誤!\n";exit(1);}
7 first->link=NULL;
8 };
9
10 void clearList(LinkList &first)//清空單鏈表
11 {
12 LinkNode *q;//借用指針
13 while(first->link!=NULL)//當鏈表不空時，刪除所有的結點
14 {
15 q=first->link;
16 first->link=q->link;//保存被刪結點，從鏈表上摘下該結點
17 delete q;//刪除該結點
18 }
19 };
20
21 int Length(LinkList &first)//計算表的長度（結點個數減一）
22 {
23 LinkNode *p=first->link;
24 int count=0;
25 while(p!=NULL)
26 {
27 p=p->link;
28 count++;
29 }
30 };
31
32 int isEmpty(LinkList &first)//判斷單鏈表是否為空，為空則返回1；不空則返回0
33 {
34 return (first->link==NULL);
35 }
36
37 LinkLode* Search(LinkList &first,DataType x)//在單鏈表中查找第一個等於x的結點，查找成功則返回該結點的位置，否則返回NULL
38 {
39 LinkNode *p=first->link;
40 while(p!=NULL&&p->data!=x)
41 {
42 p=p->link;
43 }
44 return p;
45 };
46
47 LinkNode *Locate(LinkList &first,int i)//在單鏈表對第i個結點定位，函數返回第i個結點的位置，否則返回NULL
48 {
49 if(i<0)return NULL;
50 LinkNode *p=first;
51 int k=0;
52 while(P!=NULL&&k<i)
53 {
54 p=p->link;
55 k++;
56 }
57 return p;
58 };
59
60 int Insert(LinkList &first,int i,DataType x)//將新的元素x插入到表中第i個位置，如果i不合理則函數返回0，否則返回1
61 {
62 LinkNode *p=Locate(first,i-1);//調用定位函數，將p指針指向單鏈表的第i個位置
63 if(p==NULL)return 0;//如果i不合理，返回0
64 LinkNode *s=new LinkNode;
65 if(!s){cerr<<"存儲分配錯誤!\n";exit(1);}
66 s->data=x;
67 s->link=p->link;//將s鏈接到p之後
68 p->link=s;//調整p的下一個結點，指向s
69 return 1;//插入成功，函數返回1
70 };
71
72 int Remove(LinkList &first,int i,DataType &x)
73 {
74 LinkNode *p=Locate(first,i-1);//將p指向單鏈表的第i-1個位置
75 if(P==NULL||p->link==NULL)return 0;//i不合理則函數返回0
76 LinkNode *q=p->link;//用q來保存被刪的結點
77 p->link=q->link;//重新連接 將第i-1個結點和第i+1個結點鏈接
78 x=q->data;//取出被刪結點的數據
79 delete q;//刪除這個結點
80 return 1;//刪除成功則函數返回1
81 };
82
83 void Copy(LinkList &first1,LinkList &first2)
84 //函數假定鏈表first1已存在且為空，即first1的頭結點已創建且first1->link==NULL;
85 //復制鏈表first2的全部結點到空鏈表first1中
86 {
87 LinkNode *srcptr=frist2->link;//srcptr是源指針
88 LinkNode *destptr=first1;//destptr是目標鏈尾指針
89 while(srcptr->link!=NULL)//利用while循環，將first2中的每個結點復制到first1中
90 {
91 destptr->link=new LinkNode;//新結點鏈接到目標鏈尾
92 if(!destptr){cerr<<"存儲分配錯誤!\n";exit(1);}
93 destptr=destptr->link;
94 destptr->data=srcptr->data;//節點數據的傳送
95 srcptr=srcptr->link;//傳送源鏈指針到下一結點
96 }
97 destptr->link=NULL;//目標鏈收尾
98 };
View Code
