首页 > 代码库 > 有序链表的插入操作
有序链表的插入操作
C语言教材的有序单链表程序的插入我并不满意，因为链表为空，表尾等原因导致有四种情况要处理，给同学们的阅读造成困难。书上的做法较复杂的一个原因是链表是不带头结点的,所以要考虑新结点插入时会不会变成表头,
例如:当链表为空时, 插入3, 3变成表头, 再插入1, 链表为1->3, 链表头指向1, 代码必须处理这样的情况.
第一部分: 不含头结点的链表插入的非常规思路
下面我给出另外一个思路，新结点一律插入表头，这样就不要考虑链表为空的情况了。但是可能无序，可以从表头开始，相邻节点不符合次序要求交换即可，代码的逻辑非常简单，当然效率不高，因为交换(结构可能很大）的缘故。
例如 1->2， 插入3 构成 3->1->2, 先交换变成1->3->2，再交换变成1->2->3
下面是我简单的示例程序，附带说明了另外一个概念，插入的过程即是建表的过程。
1 #include <stdlib.h> 2 #include <stdio.h> 3 #include <string.h> 4 struct node /*节点的数据结构*/ 5 { 6 int num; 7 char str[20]; 8 struct node *next; 9 };10 /* * * * * * * * * * *主函数 * * * * * * * * * * * * * * * * */11 int main(void)12 {13 struct node *insert(struct node *head,char *pstr,int n); /*函数声明 */14 void print(struct node *head); /*函数声明 */15 struct node *head;16 char str[20];17 int i, n;18 head=NULL; /*做空表*/19 20 for(i=0;i<5;i++){ //仅输入5组数据21 printf("\n input inserted num name:\n"); // 号码 空格 姓名22 scanf("%d", &n);23 gets(str); /*输入姓名*/24 head=insert(head,str,n); /* 将节点插入链表*/25 print(head); /*调用函数输出节点*/26 }27 return 0;28 }29 30 /* * * * * * * * * * * * * * 插入节点函数* * * * * * * * * * * * * * * */31 struct node *insert(struct node *head,char *pstr,int n) /*插入学号为n、姓名为pstr的节点*/32 {33 struct node *p;34 p=(struct node*)malloc(sizeof(struct node)); /*分配一个新节点*/35 strcpy (p->str,pstr); /*写入节点的姓名字串*/36 p->num=n; /* 指向学号*/37 38 /*新节点插入表头*/39 p->next=head;40 head=p;41 42 while(p->next&&p->next->num<p->num)43 {44 //交换邻接结点p和p->next的值（但是保留结点的next）45 struct node t;46 struct node *pr=p->next, *pn=p->next->next;47 t=*(p->next);48 *(p->next) = *p;49 p->next->next=pn;50 *p = t;51 p->next=pr;52 53 p=p->next;54 }55 return(head);/* 返回链表的头指针*/56 }57 58 59 /* * * * * * * * * * * * * * 链表输出函数* * * * * * * * * * * * * */60 void print (struct node *head)61 {62 struct node *temp;63 temp=head;64 printf("output strings:\n");65 while (temp!=NULL)66 {67 printf("%d -- %s\n",temp->num,temp->str);68 temp=temp->next;69 }70 return;71 }
输入如下
input inserted num name:
1 zhang
output strings:
1 -- zhang
input inserted num name:
2 li
output strings:
1 -- zhang
2 -- li
input inserted num name:
3 zhao
output strings:
1 -- zhang
2 -- li
3 -- zhao
input inserted num name:
4 qian
output strings:
1 -- zhang
2 -- li
3 -- zhao
4 -- qian
input inserted num name:
5 chen
output strings:
1 -- zhang
2 -- li
3 -- zhao
4 -- qian
5 -- chen
第二部分:带头结点的做法,我们分配一个结点永远做为链表头, 这样的话新插入的结点总是在后面,就没有前面提到的烦恼了.
1 #include <stdlib.h> 2 #include <stdio.h> 3 #include <string.h> 4 struct node /*节点的数据结构*/ 5 { 6 int num; 7 char str[20]; 8 struct node *next; 9 };10 /* * * * * * * * * * *主函数 * * * * * * * * * * * * * * * * */11 int main(void)12 {13 void insert(struct node *head,char *pstr,int n); /*函数声明 */14 void print(struct node *head); /*函数声明 */15 struct node *head;16 char str[20];17 int i, n;18 head=(struct node*)malloc(sizeof(struct node)); /*head指向头结点*/19 head->next=NULL;20 21 for(i=0;i<5;i++){ //仅输入5组数据22 printf("\n input inserted num name:\n"); // 号码 空格 姓名23 scanf("%d", &n);24 gets(str); /*输入姓名*/25 insert(head,str,n); /* 将节点插入链表*/26 print(head); /*调用函数输出节点*/27 }28 return 0;29 }30 31 /* * * * * * * * * * * * * * 插入节点函数* * * * * * * * * * * * * * * */32 void insert(struct node *head,char *pstr,int n) /*插入学号为n、姓名为pstr的节点*/33 {34 struct node *p;35 p=(struct node*)malloc(sizeof(struct node)); /*分配一个新节点*/36 strcpy (p->str,pstr); /*写入节点的姓名字串*/37 p->num=n; /* 指向学号*/38 39 40 /*寻找p的插入位置*/41 while(head->next&&head->next->num<p->num)42 {43 head=head->next; 44 }45 46 /*应该在head之后插入p*/47 p->next=head->next;48 head->next=p; 49 }50 51 52 /* * * * * * * * * * * * * * 链表输出函数* * * * * * * * * * * * * */53 void print (struct node *head)54 {55 struct node *temp;56 temp=head->next;57 printf("output strings:\n");58 while (temp!=NULL)59 {60 printf("%d -- %s\n",temp->num,temp->str);61 temp=temp->next;62 }63 return;64 }
行18,19就是分配头结点并初始化, 头结点的data我们不用.
因为head不会改变, 第32行insert也没有必要返回值, 而且恰好弥补了书中接口设计的缺陷. 另外其实现大大简化了,也没有第一个部分的低效问题. 这里值得注意的是第41行head->next的做法,保证了p一定插在head 和head->next之间.
头结点的另外一个变化就是第56行,head->next才是第一个有效的数据结点.