单链表运算

一 建立单链表

延续前面的定义，数据取字符型，以/n作为输入结束条件，动态建立单链表通常分为头插法和尾插法，下面将一一描述。

（1）头插法

算法思路：将新节点插入到当前节点的头部，直到读入结束标志符为止

这种方式生成的链表节点次序与输入的次序相反

头插法具体算法代码

[cpp]  view plain  copy

 

1. <pre name="code" class="cpp">LinkList CreatListH(void)  
2. {  
3.     char ch;  
4.     LinkList head;//头指针  
5.     ListNode *s;    //工作指针  
6.     head = NULL;    //链表开始为空  
7.     ch = getchar(); //读取第一个字符  
8.     while(ch!='\n')  
9.     {  
10.         s = (ListNode *)malloc(sizeof(ListNode));//生成新的节点  
11.         if（！s）  
12.         {  
13.             printf（"申请内存失败"）;  
14.             return NULL;  
15.         }  
16.                 s->data = ch; //将读入的数据放入新节点数据域  
17.                 s->next = head;head = s;  
18.                 ch = getchar(); //读入下一个字符  
19.         }  
20.                 return head;  
21. }  

（2）尾插法

算法思路：将新节点当前节点的尾部，直到读入结束标识符

这种方式生成的链表顺序与输入顺序一致，但是需要增加一个尾指针r，使其始终指向当前节点的尾节点

尾插法具体算法代码

[cpp]  view plain  copy

 

1. LinkList CreatListT(void)  
2. {  
3.     char ch;  
4.     LinkList head;//头指针  
5.     ListNode *s,*r;//工作指针  
6.     head = NULL;    //链表开始为空  
7.     r = NULL;  
8.     ch = getchar(); //读入第一个字符  
9.     while(ch!='\n')  
10.     {  
11.         s = (ListNode *)malloc(sizeof(ListNode));//生成新节点  
12.         if（！s）  
13.         {  
14.             printf（"申请内存失败"）;  
15.             return NULL;  
16.         }  
17.         s->data = ch;//将读入的数据放入新节点的数据域  
18.         if(head==NULL)  
19.             head = s;   //将新节点插入空表  
20.         else  
21.             r->next = s;//将新节点插入到*r之后  
22.         ch = getchar();//读入下一个字符  
23.     }  
24.     if(r!=NULL)  
25.         r->next = NULL;//对于非空表，将表尾指向指针域，置空head=s  
26.     return head;  
27. }  

注：以上俩个方法时间复杂度均为O（n）

二 单链表查找

（1）按序号查找

计数器j置为0后，扫描指针p指针从链表的头结点开始顺着链扫描。当p扫描下一个结点时，计数器j相应地加1。当j=i时，指针p所指的结点就是要找的第i个结点。而当p指针指为null且j≠i时，则表示找不到第i个结点。
注意：头结点可看做是第0个结点。

算法思想：

[cpp]  view plain  copy

 

1. ListNode * GetNode(LinkList head,int i)  
2. {  
3.     //在带头结点的单链表head中查找第i个结点，若找到（0≤i≤n），  
4.       //则返回该结点的存储位置，否则返回NULL  
5.     int j;  
6.     ListNode *p;  
7.     p = head,j = 0;//从头开始扫描  
8.     while(p->next&&j<i){  
9.         p = p->next;  
10.         j++;  
11.     }  
12.     if(i==j)  
13.         return p;//找到了第i个结点  
14.     else   
15.         return NULL；  
16. }  

算法分析：

最多距离为i，这与气位置有关，在等概率假设情况下，平均时间复杂度为

（2）按值查找

算法思想：

[cpp]  view plain  copy

 

1. ListNode * LocateNode(ListNode head,DataType key)  
2. {  
3.     ListNode *p = head->next;//设置开始比较的节点  
4.     while(p&&p->data!=key)//直到p为NULL或者p->data为key  
5.         p = p->next;//扫描下一个节点  
6.     return  p;  
7. }  

算法分析：

　该算法的执行时间亦与输入实例中key的取值相关，其平均时间复杂度分析类似于按序号查找，为O(n)。

三 插入运算

插入运算思想 ：将值为x的新结点插入到表的第i个结点的位置上，即插入到ai-1与ai之间。

具体步骤： 
（1）找到ai-1存储位置p
（2）生成一个数据域为x的新结点*s
（3）令结点*p的指针域指向新结点
（4）新结点的指针域指向结点ai。

具体算法实现 ：

[cpp]  view plain  copy

 

1. void InsertList(LinkList head,DataType x,int i)  
2. {  
3.     //将值为x的新节点插入到带头结点单链表head  
4.     //的第i个节点位置  
5.     ListNode *p;  
6.     p = GetNode(head,i-1);//寻找第i-1个节点  
7.     if(p==NULL)  
8.         Error("position error");  
9.     s = (ListNode *)malloc(sizeof(ListNode));  
10.     s->data = x;  
11.     s->next = p->next;  
12.     p->next = s;  
13. }  

算法分析：

主要集中在GetNode上，因此时间复杂度仍旧为O(n)

四  删除运算

具体步骤： 
（1）找到ai-1的存储位置p（因为在单链表中结点ai的存储地址是在其直接前趋结点ai-1的指针域next中）
（2）令p-＞next指向ai的直接后继结点（即把ai从链上摘下）
（3）释放结点ai的空间，将其归还给"存储池"。
记得释放内存就好

具体算法实现：

[cpp]  view plain  copy

 

1. void DeleteList(LinkList head ,int i)  
2. {  
3.     //删除带头结点的第i个节点  
4.     ListNode *p,*r;  
5.     p = GetNode(head,i-1);//找到第i-1个节点  
6.     if(p==NULL||p->next==NULL)  
7.         Error("position error");  
8.     r  = p->next;//r指向被删除结点的ai  
9.     p->next = r->next;//将ai从链上取下  
10.     free(r);//释放节点  
11. }  

算法分析：

时间复杂度也是O(n)

转载：http://blog.csdn.net/xsf50717/article/details/39899193