数据结构-2-单链表的实现

学习资料：数据结构（C语言版）清华大学出版社

部分函数的解释来源于百度百科。

线性表的链式表示与实现

线性表的链式表示：用一组任意的存储单元存储线性表的数据元素（这组存储单元可以是连续的，可以是不连续的）。

结点：其包括存储数据元素信息的域（数据域）和存储直接后继存储位置的域称为指针域。

单链表的特点：链表的存取必须由头指针开始。最后一个元素插入元素的时候，需要遍历整个链表。表长是一个隐含的值。在链表中，元素的“位序”概念淡化，节点的“位置”概念强化。

弱点：如果要取一个数据元素，必须从头指针出发寻找，是非随机存储的存储结构。（但其实在总体操作上个人感觉比顺序表更为方便啊！）

一、准备阶段：

1、开始前关于程序的头文件和宏定、辅助定义等相关代码如下：

 1 #include<stdio.h>
 2 #include<stdlib.h>
 3 #include<iostream>
 4 using namespace std;
 5 #define TRUE 1
 6 #define FALSE 0
 7 #define OK 1
 8 #define ERROR 0
 9 #define OVERFLOW -2
10 #define LIST_INIT_SIZE 100
11 #define LISTINCREMENT 10
12 
13 typedef int Status;
14 typedef int ElemType;

2、用结构指针来描述单链表。

1 typedef struct LNode
2 {
3     ElemType data;
4     struct LNode *next;
5 } LNode,*LinkList;

在这个代码实现的单链表中，会附加生成一个头结点。数据域为空。

二、相关函数

1、线性链表的初始化

这是一个从表尾到表头逆向建立的单链表算法。时间复杂度为O(n)。每次改变”头“节点的指针。建立一个带头结点的单链表，生成新结点并且为之分配sizeof（LNode）的存储空间。

 1 void CreatList(LinkList &L,int n)//逆位序输入n个元素的值，建立带表头结点的单链线性表L。
 2 {
 3     LinkList p;
 4     L=(LinkList)malloc(sizeof(LNode));//头结点
 5     L->next=NULL;
 6     for(int i=n; i>0; i--)
 7     {
 8 
 9         p=(LinkList)malloc(sizeof (LNode));//新节点的生成
10         cin>>p->data;
11         p->next=L->next;//插入到表头
12         L->next=p;
13     }
14 }

2、线性表的遍历输出

同样，为了调试代码，遍历输出单链表的数据是我的好帮手。用一个p指针指向L（头结点），然后遍历输出数据域里面的数据。注意：上面初始化线性表时输入数据时是逆序输入，这里就是顺序输入出。

 1 void PrintList(LinkList &L)
 2 {
 3     LNode *p;
 4     p=L->next;
 5     while(p)
 6     {
 7         cout<<p->data<<" ";
 8         p=p->next;
 9     }
10     cout<<endl;
11 }

3、获取指定位置结点的元素值。

函数功能：获取单链表L指定位置pos的元素值。在这里要考虑输入的pos值是否合法。

 1 Status GetElem (LinkList L,int pos,ElemType &e)
 2 {
 3     //L为带头结点的单链表的头指针。当第pos个元素存在时，其値赋给e并且返回OK，否则返回ERROR。
 4     LNode *p;
 5     p=L->next;
 6     int j=1;
 7     while(p&&j<pos)
 8     {
 9         p=p->next;
10         j++;
11     }
12     if(!p||j>pos)
13         return ERROR;
14     e=p->data;
15     return OK;
16 }

4、数据的插入

函数功能：在指定的结点位置插入一个结点。

算法描述：找到pos的前继元素，同样对于输入的pos值需要是否越界的判断。找到前继元素后使前继元素的指针域指向新生成的用于存放数据e的结点，使e的指针域指向位于原pos位置的结点的地址。

 1 Status ListInsert(LinkList &L,int pos,ElemType e)
 2 {
 3     LNode *p,*s;
 4     p=L;
 5     int j=0;
 6     while(p&&j<pos-1)//找到pos的前继元素。
 7     {
 8         p=p->next;
 9         j++;
10     }
11     if(!p||j>pos-1)return ERROR;
12     s=(LinkList)malloc(sizeof(LNode));
13     s->data=e;
14     s->next=p->next;
15     p->next=s;
16 }

5、数据的删除

函数功能：删除指定位置的数据。

算法描述：同样需要对pos值进行合法判断（以后对于一个输入值是否越界等判断均称之为合法判断），找到pos结点，使前继结点的指针域存放pos位置结点后继结点的地址。用free释放原pos位置的结点的内存空间。

 1 Status Delete(LinkList &L,int pos,ElemType &e)
 2 {
 3     LNode *p,*q;
 4     p=L;
 5     int j=0,i;
 6     while(p->next&&j<i-1)
 7     {
 8         p=p->next;
 9         j++;
10     }
11     if(!(p->next)||j>i-1)return ERROR;
12     q=p->next;
13     p->next=q->next;
14     e=q->data;
15     free(q);
16     return OK;
17 }

使用到了一个函数free：

函数名: free

头文件：malloc.h或stdlib.h

功能：释放malloc(或calloc、realloc)函数给指针变量分配的内存空间的函数

使用后该指针变量一定要重新指向NULL，防止野指针出现，有效规避误操作。

与malloc()函数配对使用，释放malloc函数申请的动态内存。（另：对于free(p)这句语句，如果p 是NULL 指针，那么free 对p 无论操作多少次都不会出问题。如果p 不是NULL 指针，那么free 对p连续操作两次就会导致程序运行错误。）

6、两个链表的归并

功能：使两个链表Lb和La按照原来的非递减次序依次并归。返回归并后指向头结点的指针。

算法描述：找到Lb的头结点使之作为并归后的头结点，并归，当其中一个链表并归完了，只要将另一个表的剩余段链接在pc所指的结点之后。

 1 Status Delete(LinkList &L,int pos,ElemType &e)
 2 {
 3     LNode *p,*q;
 4     p=L;
 5     int j=0,i;
 6     while(p->next&&j<i-1)
 7     {
 8         p=p->next;
 9         j++;
10     }
11     if(!(p->next)||j>i-1)return ERROR;
12     q=p->next;
13     p->next=q->next;
14     e=q->data;
15     free(q);
16     return OK;
17 }

三、主函数

对每一个函数编写完以后都有一个函数的调试测试。

 1 int main ()
 2 {
 3     LNode *L1;
 4     CreatList(L1,5);
 5     PrintList(L1);
 6 
 7     cout<<"GetElem test:"<<endl<<"PLease input a legal position:"<<endl;
 8     int pos,poi;
 9     cin>>pos;
10     GetElem(L1,pos,poi);
11     cout<<"The position of "<<pos<<" is "<<poi<<"."<<endl;
12 
13     cout<<"Insert test:"<<endl<<"Please input a legal position and the data that you want to insert."<<endl;
14     int ele;
15     cin>>pos>>ele;
16     ListInsert(L1,pos,ele);
17     PrintList(L1);
18 
19     cout<<"Delete test:"<<endl<<"Please input a legal position and the data that you want to insert."<<endl;
20     cin>>pos;
21     Delete(L1,pos,ele);
22     cout<<"The data tha you delete is "<<ele<<" .Delete successful."<<endl;
23     PrintList(L1);
24 
25     LNode *L3,*L2;
26     CreatList(L2,5);
27     PrintList(L2);
28 
29     MergeList(L2,L1,L3);
30     PrintList(L3);
31     return 0;
32 }

四、个人收获与思考

链表感觉操作上应该是更为方便。待我把整本数据结构的基础代码都实现了以后会回来增加一些功能代码比如排序、倒置之类的。

好奇书上关于mergeList函数的算法，对于链表，明明就可以使la的尾结点指向lb头结点的next这样归并啊……诶，上机出来结果的感觉是一样的。有空试试重新编写一个merge函数看看好使不……

有一点比较愧疚，（QAQ;;）我知道偷小懒是不应该的，但是由于本人学习上的进度比较慢，在这里所有的代码实现鲁棒性都很低，一旦输入错误的数据都是几乎直接反馈error值然后结束程序……待我以后学完整本数据结构时可能会找一些略带难度和综合应用性比较强的实验来做，到时候会考虑比较周全。这里偏向顾及知识点。代码的缺陷还是很大的。好比一个玩偶只有了基本的衣服可以穿上街可以不害臊，可是衣服并不光鲜亮丽。怎么说呢，哎！一步一步慢慢来。

受本人知识水平和能力的限制。描述中会有疏漏和错误的地方。欢迎读者批评和指正。一定会改正的。

啊，加油！

^q^