线性表之二，SLINKLIST(单链表)类，模板类及C链表（增删改查，广义表

一、SLINKLIST(单链表)类，模板类

  1 /*
  2     该文件按习惯可以分成.h文件和实现的.cpp文件
  3  */
  4 template <class elemType>
  5 class sLinkList
  6 {
  7 private:
  8     struct node{ //定义单链表中的结点结构
  9         elemType data;
 10         node *next;
 11 
 12         node(const elemType &x, node *n = NULL)
 13         {
 14             data = x; next = n;;
 15         }
 16         node() :next(NULL) {}
 17         ~node() {}
 18     };
 19     
 20     node  *head;//头指针
 21     int currentLength;//表长
 22 
 23     //node *move(int i)const;//返回第i个结点的地址
 24     node *move(int i)const
 25     {
 26         node *p = head;
 27         while( i-- >= 0 )
 28         {
 29             p = p->next;
 30         }
 31         return p;
 32     } 
 33 
 34 public:
 35     sLinkList();
 36     ~sLinkList() {
 37         clear(); delete head;
 38     }
 39 
 40     void clear();
 41     int length()const {
 42         return currentLength;
 43     }
 44     void insert(int i, const elemType&x);
 45     void remove(int i);
 46     int search(const elemType&x)const;
 47     elemType visit(int i)const;
 48     void traverse()const;
 49 };
 50 
 51 // sLinkList
 52 template <class elemType>
 53 sLinkList<elemType> ::sLinkList()
 54 {
 55     head = new node;
 56     currentLength = 0;
 57 }
 58 
 59 // clear
 60 template <class elemType>
 61 void sLinkList<elemType> ::clear()
 62 {
 63     node *p = head->next, *q;
 64     head->next = NULL;
 65     while(p!=NULL)
 66     {
 67         q = p->next;
 68         delete p;
 69         p = q;
 70     }
 71     currentLength = 0;
 72 }
 73 
 74 // insert
 75 template <class elemType>
 76 void sLinkList<elemType> ::insert(int i, const elemType&x)
 77 {
 78     node *pos;
 79     pos = move(i-1);
 80     pos->next = new node(x, pos->next);
 81     ++currentLength;
 82 }
 83 
 84 /* // 类外实现,编译器编译不过,只好类内实现
 85 // move
 86 template <class elemType>
 87 sLinkList<elemType>::node *sLinkList<elemType> :: move(int i)const
 88 {
 89     node *p = head;
 90     while( i-- >= 0 )
 91     {
 92         p = p->next;
 93     }
 94     return p;
 95 }  */
 96 
 97 // search
 98 template <class elemType>
 99 int sLinkList<elemType> :: search(const elemType&x)const
100 {
101     node *p = head->next;
102     int i=0;
103     while( p != NULL && p->data != x )
104     {
105         p = p->next;
106         ++i;
107     }
108     
109     if(p == NULL)
110         return -1;
111     else
112         return i;
113 }    
114 
115 // visit
116 template <class elemType>
117 elemType sLinkList<elemType> :: visit(int i)const
118 {
119     return move(i)->data;
120 }    
121 
122 // traverse
123 template <class elemType>
124 void sLinkList<elemType> :: traverse()const
125 {
126     node *p = head->next;
127     cout<<endl;
128     
129     while( p != NULL )
130     {
131         cout<<p->data<<" ";
132         p = p->next;
133     }
134     
135     cout<<endl;
136 }    
137 
138 // remove
139 template <class elemType>
140 void sLinkList<elemType> :: remove(int i)
141 {
142     node *pos, *delp;
143     pos = move(i-1);
144     delp = pos->next;
145     
146     pos->next = delp->next;
147     delete delp;
148     
149     --currentLength;
150 }

sLinkList模板类（单链表代码）

二、C语言链表（增删改查）

1.删除一个元素，删除所有相同元素：

  1 #include <stdio.h>
  2 #include <stdlib.h>
  3 #include <conio.h>
  4 
  5 /*定义结构体*/
  6 struct student
  7 {
  8     int num;
  9     float score;
 10     struct student *next;
 11 };
 12 
 13 /*创建一个只有头结点的空链表*/
 14 struct student *create_head()
 15 {
 16     struct student *head;
 17     head=(struct student*)malloc(sizeof (struct student) );
 18     if(head==NULL)      //小心别漏这个
 19     {
 20         printf("申请头结点失败!
");
 21         return NULL;
 22     }
 23     head->next=NULL;
 24     return head;
 25 }
 26 /*将s指向的结点插入链表,使链表保持升序,并返回头结点*/
 27 struct student *insert(struct student *head,struct student *s)
 28 {
 29     struct student *p=head;
 30     while(p->next!=NULL&&s->score>p->next->score){
 31     //特别注意&&左右不能写反,若s最大,最后p->next=NULL,p->next->score运行出错
 32         p=p->next;
 33     }
 34     if(p->next==NULL) //s->score最大的情况//其实两种情况可以并在一块写
 35     {
 36         p->next=s;    //连接结点
 37         s->next=NULL;   //p->next就等于NULL
 38     }
 39     else  //连接结点
 40     {
 41         s->next=p->next;
 42         p->next=s;    
 43     }
 44     return head ;
 45 }
 46 /*查找符合条件的结点,并返回指向该结点的指针*/
 47 struct student *search(struct student *head)
 48 {
 49     struct student *p=head->next;
 50     int num;
 51     printf("请输入要查找学生的学号:
");
 52     scanf("%d",&num);
 53     while(p!=NULL&&p->num!=num){
 54     //特别注意两条件不能写反,若写反最后p指向NULL时p->num找不到 运行出错
 55         p=p->next;
 56     }
 57     if(p==NULL)
 58     {
 59     //特别注意两个if不能调换,若调换最后p指向NULL时p->num运行出错
 60         printf("找不到符合条件的结点!!!");
 61     }
 62     else //if(p->num==num) 
 63     {
 64         printf("找到符合条件的结点
该结点为%d	%f",p->num,p->score);
 65     }
 66     return p; //返回空指针或查找到的指针
 67 }
 68 /*输出链表各结点的值,也称对链表的遍历*/
 69 void print(struct student *head)
 70 {
 71     struct student *p;
 72     p=head->next;
 73 
 74     printf("  链表如下:  
");
 75     while(p!=NULL)
 76     {
 77         printf("%d	%.1f
",p->num,p->score);
 78         p=p->next;
 79     }
 80 }
 81 
 82 /*释放链表*/
 83 void free_list(struct student *head)
 84 {
 85     struct student *p=head ;
 86     printf("释放链表:
");
 87     while(p!=NULL)
 88     {
 89         head=head->next;
 90         free(p);
 91         p=head;
 92     }
 93     printf("释放链表成功!
");
 94 }
 95 /*删除链表中值为num的结点,并返回链表的首指针*/
 96 struct student *delete_node(struct student *head,int num_x)
 97 {
 98     struct student *p1=head->next , *p2=head ;
 99     while(p1!=NULL&&p1->num!=num_x)
100     {//特别注意&&左右条件不能调换,若调换如果p1指向NULL时p1->num运行出错
101         p2=p1;
102         p1=p1->next;
103     }
104     if(p1==NULL)
105     {
106         //特别注意两个if不能调换,若调换如果p1指向NULL时,p1->num运行出错
107         printf("找不到符合删除要求的结点!!!
");
108     }
109     else //if(p1->num==num_x)
110     {
111         p2->next=p1->next;
112         free(p1);
113         printf("结点删除成功!
");
114     }
115     return head;
116 }
117 
118 /*完整的有头结点链表操作程序*/
119 int main()
120 {
121     struct student *p , *head ;
122     char c;
123     int num ;
124     float score ;
125     printf("有头结点链表操作程序:
");
126     head=create_head();
127     while(1)
128     {
129         printf("I:插入结点(自动升序)  P:输出链表 
130                S:查找结点  D:删除结点  E:释放链表并退出程序!  ");
131         c=getch();
132         switch(c)
133         {
134             case'I':
135                 printf("请分别输入要插入学生的学号和分数:
");
136                 scanf("%d%f",&num,&score);
137                 p=(struct student*)malloc( sizeof(struct student) );
138                 if(p==NULL)
139                 {
140                     printf("申请该结点失败!!!
");
141                     exit (0) ;
142                 }
143                 p->num=num;  p->score=score;   //给p赋值
144                 insert(head,p);
145                 printf("插入成功!
");
146                 break;
147             case'P':
148                 print(head);
149                 break;
150             case'S':
151                 search(head);
152                 break;
153             case'D':
154                 printf("请输入要删除的学生的学号:
");
155                 scanf("%d",&num);
156                 delete_node(head,num);
157                 break;
158             case'E':
159                 free_list(head);
160                 exit (0);
161         }
162     }
163     return 0;
164 }

增删改查

  1 #include <stdio.h>
  2 #include <stdlib.h>
  3 #include <conio.h>
  4 
  5 /*定义结构体*/
  6 struct node{
  7     int num;
  8     struct node *next;
  9 };
 10 
 11 /*创建一个只有头结点的空链表*/
 12 struct node *create_head()
 13 {
 14     struct node *head;
 15     head = (struct node*)malloc(sizeof (struct node) );
 16     
 17     if(head == NULL)   //小心别漏这个
 18     {
 19         printf("申请头结点失败!
");
 20         return NULL;
 21     }
 22     head->next = NULL;
 23     return head;
 24 }
 25 
 26 /*将s指向的结点插入链表,使链表保持升序,并返回头结点*/
 27 struct node *insert(struct node *head,int num)
 28 {    
 29     struct node *p = head, *s;
 30     s = (struct node*)malloc( sizeof(struct node) );
 31     if(s == NULL)
 32     {
 33         printf("申请该结点失败!!!
");
 34         exit (0) ;
 35     }
 36     s->num = num; //给p赋值
 37     
 38     while(p->next != NULL && s->num >= p->next->num){
 39     //特别注意&&左右不能写反,若s最大,最后p->next=NULL,p->next->num运行出错
 40         p = p->next;
 41     }
 42    
 43     s->next = p->next; //若s最大, p->next=NULL
 44     p->next = s;   
 45     printf("插入成功!
");
 46     
 47     return head ;
 48 }
 49 
 50 /*输出链表各结点的值,也称对链表的遍历*/
 51 void print(struct node *head)
 52 {
 53     struct node *p;
 54     p = head->next;
 55     
 56     if(!p){
 57         printf("链表为空
");
 58         return;
 59     }
 60 
 61     printf("链表如下:  
");
 62     while(p!=NULL)
 63     {
 64         printf("%d	",p->num);
 65         p = p->next;
 66     }
 67     printf("
");
 68 }
 69 
 70 /* 删除链表所有值为num的结点 */
 71 struct node *delete_num(struct node *head,int num)
 72 {
 73     int flag = 1;
 74     struct node *p1 = head->next , *p2 = head ;
 75     if(p1 == NULL){
 76         printf("链表为空
");
 77         return head;
 78     }
 79     
 80     while(p1 != NULL){ 
 81         if(p1->num == num){    //找到，删除
 82             p2->next = p1->next; //链接后续元素
 83             free(p1); // 删除元素
 84             printf("结点删除成功!
");
 85             flag = 0;
 86             p1 = p2->next;    //p1指向后续元素        
 87         }
 88         else{    //没找到，指针后移    
 89             p2 = p1; //保持p2在p1前面
 90             p1 = p1->next; //指针后移
 91         }       
 92     }
 93     
 94     if(flag){
 95         printf("找不到符合删除要求的结点!!!
");
 96     }
 97         
 98     return head;
 99 }
100 
101 int main()
102 {
103     struct node *head ;
104     char c;  
105     int num ;
106     printf("有头结点链表操作程序:
");
107     head = create_head();
108     
109     while(1)
110     {
111         printf("i:插入结点(自动升序) p:输出链表 d:删除结点 e:退出 
");
112         c = getch();
113         switch(c)
114         {
115             case'i':
116                 printf("请输入要插入的数据:
");
117                 scanf("%d",&num);          
118                 insert(head,num);
119                 break;
120             case'p':
121                 print(head);
122                 break;           
123             case'd':               
124                 printf("请输入要删除结点的数据:
");
125                 scanf("%d",&num);
126                 delete_num(head,num);                
127                 break; 
128             case'e':  
129                 exit (0) ;
130         }
131     }
132     return 0;
133 }

删除所有值为num的结点

2. 删除一个或多个元素，使用函数指针

  1 #include <stdio.h>
  2 #include <stdlib.h>
  3 #include <conio.h>
  4 
  5 /*定义结构体*/
  6 struct node{
  7     int num;
  8     struct node *next;
  9 };
 10 
 11 /*创建一个只有头结点的空链表*/
 12 struct node *create_head()
 13 {
 14     struct node *head;
 15     head = (struct node*)malloc(sizeof (struct node) );
 16     
 17     if(head == NULL)   //小心别漏这个
 18     {
 19         printf("申请头结点失败!
");
 20         return NULL;
 21     }
 22     head->next = NULL;
 23     return head;
 24 }
 25 
 26 /*将s指向的结点插入链表,使链表保持升序,并返回头结点*/
 27 struct node *insert(struct node *head,int num)
 28 {    
 29     struct node *p = head, *s;
 30     s = (struct node*)malloc( sizeof(struct node) );
 31     if(s == NULL)
 32     {
 33         printf("申请该结点失败!!!
");
 34         exit (0) ;
 35     }
 36     s->num = num; //给p赋值
 37     
 38     while(p->next != NULL && s->num >= p->next->num){
 39     //特别注意&&左右不能写反,若s最大,最后p->next=NULL,p->next->num运行出错
 40         p = p->next;
 41     }
 42    
 43     s->next = p->next; //若s最大, p->next=NULL
 44     p->next = s;   
 45     printf("插入成功!
");
 46     
 47     return head ;
 48 }
 49 
 50 /*输出链表各结点的值,也称对链表的遍历*/
 51 void print(struct node *head)
 52 {
 53     struct node *p;
 54     p = head->next;
 55     
 56     if(!p){
 57         printf("链表为空
");
 58         return;
 59     }
 60 
 61     printf("链表如下:  
");
 62     while(p!=NULL)
 63     {
 64         printf("%d	",p->num);
 65         p = p->next;
 66     }
 67     printf("
");
 68 }
 69 
 70 /* 删除元素 */
 71 struct node *delete_num(struct node *head,int (*del)(int a,int b,int c),int num1, int num2=0)
 72 {
 73     int flag = 1;
 74     struct node *p1 = head->next , *p2 = head ;
 75     if(p1 == NULL){
 76         printf("链表为空
");
 77         return head;
 78     }
 79     
 80     while(p1 != NULL){ 
 81         if(del(p1->num,num1,num2)){    //找到，删除
 82             p2->next = p1->next; //链接后续元素
 83             free(p1); // 删除元素
 84             printf("结点删除成功!
");
 85             flag = 0;
 86             p1 = p2->next;    //p1指向后续元素        
 87         }
 88         else{    //没找到，指针后移    
 89             p2 = p1; //保持p2在p1前面
 90             p1 = p1->next; //指针后移
 91         }       
 92     }
 93     
 94     if(flag){
 95         printf("找不到符合删除要求的结点!!!
");
 96     }
 97         
 98     return head;
 99 }
100 
101 //删除一个或多个
102 int del(int a,int b,int c){
103     if(c==0){
104         return a==b;
105     }
106     return a>=b && a<=c;
107 }
108 
109 int main()
110 {
111     struct node *head ;
112     char c,c1;  
113     int num1, num2 ;
114     printf("有头结点链表操作程序:
");
115     head = create_head();
116     
117     while(1)
118     {
119         printf("i:插入结点(自动升序) p:输出链表 d:删除结点 e:退出 
");
120         c = getch();
121         switch(c)
122         {
123             case'i':
124                 printf("请输入要插入的数据:
");
125                 scanf("%d",&num1);          
126                 insert(head,num1);
127                 break;
128             case'p':
129                 print(head);
130                 break;           
131             case'd':
132                 printf("1:删除一个结点 2:删除结点(范围)
");
133                 c1 = getch(); //不回显
134                 switch(c1){
135                     case '1':
136                         printf("请输入要删除的结点:
");
137                         scanf("%d",&num1);
138                         delete_num(head,del,num1); 
139                         break;
140                     case '2':
141                         printf("请输入要删除结点值的范围:
");
142                         scanf("%d%d",&num1,&num2);
143                         delete_num(head,del,num1,num2);  
144                         break;
145                 }                  
146                 break; 
147             case'e':  
148                 exit (0) ;
149         }
150     }
151     return 0;
152 }

删除一个或多个

3. 链表，删除给定值S与T之间的所有元素

  1 #include <stdio.h>
  2 #include <stdlib.h>
  3 #include <conio.h>
  4 
  5 /*定义结构体*/
  6 struct node{
  7     int num;
  8     struct node *next;
  9 };
 10 
 11 /*创建一个只有头结点的空链表*/
 12 struct node *create_head()
 13 {
 14     struct node *head;
 15     head = (struct node*)malloc(sizeof (struct node) );
 16     
 17     if(head == NULL)   //小心别漏这个
 18     {
 19         printf("申请头结点失败!
");
 20         return NULL;
 21     }
 22     head->next = NULL;
 23     return head;
 24 }
 25 
 26 /*将s指向的结点插入链表,使链表保持升序,并返回头结点*/
 27 struct node *insert(struct node *head,int num)
 28 {    
 29     struct node *p = head, *s;
 30     s = (struct node*)malloc( sizeof(struct node) );
 31     if(s == NULL)
 32     {
 33         printf("申请该结点失败!!!
");
 34         exit (0) ;
 35     }
 36     s->num = num; //给p赋值
 37     
 38     while(p->next != NULL && s->num >= p->next->num){
 39     //特别注意&&左右不能写反,若s最大,最后p->next=NULL,p->next->num运行出错
 40         p = p->next;
 41     }
 42    
 43     s->next = p->next; //若s最大, p->next=NULL
 44     p->next = s;   
 45     printf("插入成功!
");
 46     
 47     return head ;
 48 }
 49 
 50 /*输出链表各结点的值,也称对链表的遍历*/
 51 void print(struct node *head)
 52 {
 53     struct node *p;
 54     p = head->next;
 55     
 56     if(!p){
 57         printf("链表为空
");
 58         return;
 59     }
 60 
 61     printf("链表如下:  
");
 62     while(p!=NULL)
 63     {
 64         printf("%d	",p->num);
 65         p = p->next;
 66     }
 67     printf("
");
 68 }
 69 
 70 /* 删除给定值num1与num2之间的所有元素 */
 71 struct node *delete_num(struct node *head,int num1, int num2)
 72 {
 73     int flag = 1;
 74     struct node *p1 = head->next , *p2 = head ;
 75     if(p1 == NULL){
 76         printf("链表为空
");
 77         return head;
 78     }
 79     
 80     while(p1 != NULL){ 
 81         if(p1->num >= num1 && p1->num <=num2){    //找到，删除
 82             p2->next = p1->next; //链接后续元素
 83             free(p1); // 删除元素
 84             printf("结点删除成功!
");
 85             flag = 0;
 86             p1 = p2->next;    //p1指向后续元素        
 87         }
 88         else{    //没找到，指针后移    
 89             p2 = p1; //保持p2在p1前面
 90             p1 = p1->next; //指针后移
 91         }       
 92     }
 93     
 94     if(flag){
 95         printf("找不到符合删除要求的结点!!!
");
 96     }
 97         
 98     return head;
 99 }
100 
101 int main()
102 {
103     struct node *head ;
104     char c;  
105     int num1, num2 ;
106     printf("有头结点链表操作程序:
");
107     head = create_head();
108     
109     while(1)
110     {
111         printf("i:插入结点(自动升序) p:输出链表 d:删除结点(范围) e:退出 
");
112         c = getch();
113         switch(c)
114         {
115             case'i':
116                 printf("请输入要插入的数据:
");
117                 scanf("%d",&num1);          
118                 insert(head,num1);
119                 break;
120             case'p':
121                 print(head);
122                 break;           
123             case'd':               
124                 printf("请输入要删除结点值的范围:
");
125                 scanf("%d%d",&num1,&num2);
126                 delete_num(head,num1,num2);                
127                 break; 
128             case'e':  
129                 exit (0) ;
130         }
131     }
132     return 0;
133 }

链表，删除区间元素

4、链表逆序

  1 #include <stdio.h>
  2 #include <malloc.h>
  3 
  4 /* 定义链表结点 */
  5 typedef struct node NODE;
  6 typedef struct node* Linklist;
  7 struct node{
  8     int data;
  9     Linklist next;
 10 };
 11 
 12 /* 逆序链表 */
 13 Linklist reverse(Linklist L, Linklist next)
 14 {
 15     if(next == NULL)
 16         return L;
 17     Linklist head = reverse(L->next, next->next);//一直压栈
 18     next->next = L;//退栈逆序(前驱成后继)
 19     L->next = NULL;  //保证逆序前的第一个结点的next为NULL
 20     return head;//传递逆序前的最后一个结点的指针
 21 } 
 22 void reverse(Linklist L)//包装逆序函数
 23 {
 24     if(L == NULL || L->next == NULL)
 25         return; //指针为空或链表为空
 26     L->next = reverse(L->next, L->next->next);
 27 } 
 28 
 29 /* 
 30 //利用前后三个指针逐个结点逆序
 31 void reverse(Linklist L)
 32 {
 33     Linklist NEW = NULL, CUR = L->next, TEMP;
 34     while(CUR)//是否空
 35     {
 36         TEMP = CUR->next;//保存新表的当前指针的前驱指针(无前驱为NULL)
 37         CUR->next = NEW;// 逆序(NEW为新表当前CUR的后继指针)
 38         NEW = CUR;//更新新表后继指针
 39         CUR = TEMP;//更新新表当前指针      
 40     }    
 41     L->next = NEW;//逆序的头指针插入头结点
 42 }  
 43 */
 44 
 45 /* 
 46 //利用前后二个指针逐个结点分割, 利用头插法逆序
 47 void reverse(Linklist L)
 48 {
 49     Linklist CUR = L->next, NEW;
 50     L->next = NULL;
 51     while(CUR)//是否空
 52     {
 53         NEW = CUR;//保存当前指针
 54         CUR = CUR->next;//当前指针更新(为新表的前驱)
 55         NEW->next = L->next;// 新结点头插法
 56         L->next = NEW; //新结点插到头结点
 57     }      
 58 }   
 59 */
 60 
 61 /* 创建带头结点的链表 */
 62 Linklist create()
 63 {
 64     printf("输入整数若干, -1结束输入:");
 65     Linklist L,p,r;
 66     L = r = (Linklist)malloc(sizeof(NODE));
 67     L->next = NULL;
 68     int x;
 69     scanf("%d",&x);
 70     while(x!=-1)
 71     {   /* 创建新结点*/
 72         p = (Linklist)malloc(sizeof(NODE));
 73         p->data = x;
 74         p->next = NULL;
 75         /* 尾插 */
 76         r->next = p;//尾插
 77         r = p;    //更新尾指针
 78         scanf("%d",&x);
 79     }
 80     return L;
 81 }
 82 
 83 /* 打印链表 */
 84 void print(Linklist L)
 85 {
 86     if(L==NULL) return;         
 87     while(L->next)//传带头结点链表
 88     {
 89         L = L->next;
 90         printf("%5d",L->data);
 91     }
 92     printf("
");
 93 }
 94 
 95 int main()
 96 {    /* 创建链表并打印 */
 97     Linklist L = create();
 98     printf("原链表如下:");
 99     print(L);
100     /* 逆序并打印 */
101     reverse(L);//逆序
102     printf("逆序后如下:");
103     print(L);
104     return 0;
105 }

递归，非递归逆置

5、删除a链表若干元素插入到b链表

  1 #include <stdio.h>
  2 #include <malloc.h>
  3 /*定义结构体*/
  4 typedef struct node NODE;
  5 typedef struct node* LINKLIST;
  6 struct node{
  7     int num;
  8     LINKLIST next;
  9 };
 10 /* 创建链表 */
 11 void create(LINKLIST* a, int n)
 12 {
 13     printf("请输入%d个整数:", n);
 14     LINKLIST r, p;
 15     *a = r = p = (LINKLIST)malloc(sizeof(NODE));
 16     p->next = NULL;
 17     scanf("%d",&p->num);
 18 
 19     for(int i=1; i<n; ++i){
 20         p = (LINKLIST)malloc(sizeof(NODE));
 21         p->next = NULL;
 22         scanf("%d",&p->num);
 23         r->next = p;
 24         r = p;
 25     }    
 26 }
 27 /* 删除并插入 */
 28 LINKLIST DelAndInsert(LINKLIST a, LINKLIST b, int i, int j, int len )
 29 {    /* 删除a链表从i开始len个元素 */
 30     if(i<=0 || j<=0 || len<=0)
 31     {
 32         printf("erro
");
 33         return NULL;
 34     }
 35     
 36     LINKLIST start,end, pre, t;
 37     t = a; //保存a的地址
 38     
 39     int count = 1; //第一个元素
 40     while(t && count<i+len-1){
 41         if(count==i-1) pre = t;//start之前的元素
 42         t = t->next;
 43         count++;    
 44     }
 45     if(!t && count<i+len-1)
 46     {
 47         printf("删除位置错误
");
 48         return a;
 49     }
 50     end = t;// 确定删除结束结点end
 51     if(i>1)
 52     {            
 53         start = pre->next; //确定删除开始结点
 54         pre->next = end->next; //删除len个元素
 55     }
 56     else
 57     {
 58         start = a;  //确定删除开始元素
 59         a = end->next; //如果等于1, end后的元素地址返回        
 60     }
 61         
 62     printf("删除a链表从第%d个元素开始共%d个元素,插入到b链表第%d个元素后
",
 63         i,len,j);
 64     /* 插入到b链表从j开始 */
 65     while(b && (j-1)){
 66         b = b->next;
 67         j--;
 68     }
 69     if(!b && j>0)
 70     {
 71         printf("插入位置错误
");
 72         return a;
 73     }
 74     end->next = b->next; //第j+1个元素插到end后
 75     b->next = start;  //start插到第j个元素后
 76     return a;
 77 }
 78 /* 打印 */
 79 void print(LINKLIST a){
 80     while(a)
 81     {
 82         printf("%5d",a->num);
 83         a = a->next;
 84     }
 85     printf("
");
 86 }
 87 /*
 88 1 2 3 4 5 6 7 8 9 10
 89 11 12 13 14 15 16 
 90  */
 91 int main()
 92 {   
 93     LINKLIST a, b;
 94     //int n = 10;
 95     printf("数组a,");
 96     create(&a,10);
 97     printf("数组b,");
 98     create(&b,6);
 99     a = DelAndInsert(a,b,2,1,5);
100     printf("a链表删除后:");
101     print(a);
102     printf("b链表插入后:");
103     print(b);    
104     return 0;
105 }

删除并插入

6、链表实现约瑟夫环，猴子选大王

 1 #include <stdio.h>
 2 #include <malloc.h>
 3 
 4 struct Node {
 5     int number;
 6     struct Node* next;
 7 };
 8 
 9 struct Node* CreatLinkList(int total)
10 {
11     struct Node *p,*t,*h; //p新结点, t当前结点, h记录第一结点
12     for ( int i=total; i>=1; i--)
13     {
14         p = (struct Node*)malloc(sizeof(struct Node));
15         p->number = i;
16         p->next = NULL;
17         
18         if(i==total) t = p, h = p; //保留当前结点t第一个结点h
19         else p->next = t, t = p;//头部插入更新当前t
20     }
21 
22     h->next = t;//插到第一个结点
23     return h; //返回第一个结点, 后继结点数字1, 1的前驱结点
24 }
25 
26 void deleteNextNode(struct Node *p)
27 {
28     struct Node *t = p->next; //p的后继, 即删除的结点
29     printf("本轮出圈%d
", t->number);
30     p->next = t->next; //删除结点的后继, 链接到删除结点的前驱
31     free(t);
32 }
33 
34 int main()
35 {
36     struct Node *p = NULL;
37     int total = 5, space = 1;
38     scanf("%d%d",&total, &space);
39     
40     p = CreatLinkList(total);
41 
42     while(p != p->next)
43     {
44         for (int i = 1; i < space; i++)
45                p = p->next;//确定删除结点的前驱
46         deleteNextNode(p);
47     }
48 
49     printf("胜利者%d
", p->number);
50     free(p);
51     
52     return 0;
53 }

循环链表实现猴子选大王

7、多项式加法

  1 /* 多项式加法(链表表示法 ) */
  2 #include <stdio.h>
  3 #include <malloc.h>
  4 
  5 struct PolyNode {  
  6     int coef; // 系数  
  7     int expon;     // 指数  
  8     struct PolyNode *link;   // 指向下一个节点的指针 
  9 }; 
 10 typedef struct PolyNode *Polynomial;
 11  
 12 //Compare
 13 int Compare(int a, int b)
 14 {
 15     int ret;
 16     if(a > b) ret = 1;
 17     else if(a < b) ret = -1;
 18     else ret = 0;
 19     return ret;
 20 }
 21 
 22 //Attach
 23 void Attach( int c, int e, Polynomial *pRear )   
 24 {   /* 由于在本函数中需要改变当前结果表达式尾项指针的值， */ 
 25     /* 所以函数传递进来的是结点指针的地址，*pRear指向尾项*/      
 26     Polynomial P;         
 27     P =(Polynomial)malloc(sizeof(struct PolyNode)); /* 申请新结点 */      
 28     P->coef = c;    /* 对新结点赋值  */      
 29     P->expon = e;      
 30     P->link = NULL;  
 31     /* 将P指向的新结点插入到当前结果表达式尾项的后面  */       
 32     (*pRear)->link = P;       
 33     *pRear = P; /* 修改pRear值 */ 
 34 } 
 35 
 36 //读入链表 
 37 Polynomial Read()
 38 {
 39     Polynomial front, rear, temp; 
 40     rear = (Polynomial) malloc(sizeof(struct PolyNode));   
 41     front = rear;
 42     int c, e;
 43     int n;
 44     printf("输入多项式的项数:");
 45     scanf("%d", &n);//n个结点
 46     printf("按指数递减顺序逐项输入多项式系数指数:");
 47     for(int i=0; i<n; i++)
 48     {       
 49         scanf("%d %d", &c, &e);
 50         Attach( c, e, &rear);     
 51     }
 52     
 53     temp = front; 
 54     front = front->link; 
 55     free(temp); 
 56     return front;  
 57 }
 58 
 59 //加法运算 
 60 Polynomial  PolyAdd (Polynomial P1, Polynomial P2) 
 61 { 
 62     Polynomial front, rear, temp; 
 63     int sum; 
 64     rear = (Polynomial) malloc(sizeof(struct PolyNode));   
 65     front = rear;        /* 由front 记录结果多项式链表头结点 */ 
 66 
 67     while ( P1 && P2 )  /* 当两个多项式都有非零项待处理时 */ 
 68     switch ( Compare(P1->expon, P2->expon) ) 
 69     { 
 70         case 1: Attach( P1->coef, P1->expon, &rear); 
 71                 P1 = P1->link; 
 72                 break; 
 73         case -1:Attach(P2->coef, P2->expon, &rear);  
 74                 P2 = P2->link; 
 75                 break; 
 76         case 0: sum = P1->coef + P2->coef;            
 77                 if ( sum ) Attach(sum, P1->expon, &rear);            
 78                 P1 = P1->link;             
 79                 P2 = P2->link;            
 80                 break; 
 81     } 
 82     /* 将未处理完的另一个多项式的所有节点依次复制到结果多项式中去 */ 
 83     for ( ; P1; P1 = P1->link ) Attach(P1->coef, P1->expon, &rear); 
 84     for ( ; P2; P2 = P2->link ) Attach(P2->coef, P2->expon, &rear); 
 85     //rear->link = NULL;  //Attach函数link域已经赋值NULL
 86     temp = front; 
 87     front = front->link; /*令front指向结果多项式第一个非零项 */ 
 88     free(temp);           /* 释放临时空表头结点 */ 
 89     return front; 
 90 }  
 91 
 92 //打印
 93 void Print(Polynomial P)
 94 {
 95     while(P)
 96     {      
 97         printf("%3d%3d ", P->coef, P->expon);              
 98         P = P->link;
 99     }
100     printf("
");
101 }
102 
103 int main()
104 {
105     Polynomial  P1, P2; 
106     P1 = Read(); //链表P1
107     P2 = Read(); //链表P2
108     Print(PolyAdd(P1,P2)); //打印加法结果
109     return 0;
110 }

链表多项式加法

8、链表合并

  1 /* 
  2 假设两个按元素值递增有序排列的线性表A和B，均以单链表作为存储结构，
  3 请编写算法，将A表和B表归并成一个按元素值递减有序排列的线性表C，
  4 并要求利用原表的（即A表和B表的）结点空间存放表C 
  5 算法：
  6 1、题目要求利用原链表结点空间，把链表A的头结点作为链表C的头结点；
  7 2、把链表A B的表头结点分别赋值给两个指针，比较元素值大小依次向后移动取结点；
  8 3、把取到的结点按头插法插入到链表C的头结点，会产生从大到小的顺序；
  9 4、算法采用了c++的引用的概念，避免c的指针的指针的表达；
 10 注意：
 11 1、把链表A的头结点作为链表C的头结点注意把其指针域置空，因为用的头插法；
 12 2、元素值的判断注意用if else语句，涉及到指针；
 13 3、头插法会修改结点指针域，要提前保存下一个结点的指针；
 14 4、记得释放链表B的头结点并置空；
 15 */
 16 
 17 #include <stdio.h>
 18 #include <stdlib.h>
 19 #include <limits.h>
 20 
 21 typedef struct node LinklistNode;
 22 typedef struct node* Linklist;
 23 struct node{
 24      int data;
 25      Linklist next;
 26 };
 27 
 28 /* 新结点 */
 29 Linklist NewNode(int d)
 30 {
 31     Linklist L = (Linklist)malloc(sizeof(LinklistNode));
 32     L->data = d;
 33     L->next = NULL;
 34     return L;
 35 }
 36 
 37 /* 头插 */
 38 void HeadInsert(Linklist& Head, Linklist L)
 39 {
 40     L->next = Head->next;
 41     Head->next = L;
 42 }
 43 
 44 /* 尾插 */
 45 void TailInsert(Linklist& Tail, Linklist L)
 46 {
 47     Tail->next = L;
 48     Tail = L;
 49 }
 50 
 51 /* 创建链表 */
 52 Linklist CreateLinklist()
 53 {
 54     printf("从小到大输入整数若干, -1结束输入:");
 55     Linklist L,p,r;
 56     L = r = NewNode(INT_MAX);/* 创建头结点 */
 57     /* 循环插入链表结点 */
 58     int x;
 59     scanf("%d",&x);
 60     while(x!=-1)
 61     {   /* 创建新结点*/
 62         p = NewNode(x);
 63         /* 尾插 */
 64         TailInsert(r,p);
 65         scanf("%d",&x);
 66     }
 67     return L;
 68 }
 69 
 70 Linklist MergeLinklist(Linklist& L1, Linklist& L2)
 71 {
 72     Linklist pL1 = L1->next, pL2 = L2->next, tmp = NULL;
 73     L1->next = NULL;  /* L1的头指针作为新链表的头指针 */
 74     while(pL1 && pL2)
 75     {
 76         if(pL1->data <= pL2->data){
 77             tmp = pL1->next;  /* 保存下一个结点 */
 78             HeadInsert(L1,pL1); /* 因为头插法会修改结点的指针域 */
 79             pL1 = tmp;
 80         }
 81         else{
 82             tmp = pL2->next;
 83             HeadInsert(L1,pL2);
 84             pL2 = tmp;
 85         }
 86     }
 87     while(pL1)
 88     {
 89         tmp = pL1->next;
 90         HeadInsert(L1,pL1);
 91         pL1 = tmp;
 92     }
 93     while(pL2)
 94     {
 95         tmp = pL2->next;
 96         HeadInsert(L1,pL2);
 97         pL2 = tmp;
 98     }
 99     free(L2); /* 释放L2的头结点 */
100     L2 = NULL;
101     return L1;
102 }
103 
104 void PrintLinklist(Linklist L)
105 {
106     L = L->next;
107     while(L)
108     {
109         printf("->%d", L->data);
110         L = L->next;
111     }
112     printf("
");
113 }
114 /* 
115 1 2 4 9 -1
116 4 5 6 7 8 9 -1
117 */
118 int main()
119 {
120     Linklist L1 = CreateLinklist();
121     Linklist L2 = CreateLinklist();
122     PrintLinklist(L1);
123     PrintLinklist(L2);
124     PrintLinklist(MergeLinklist(L1,L2));    
125     return 0;
126 }

合并，逆转链表

9、链式字符串匹配

#include <stdio.h>
#include <stdlib.h>

/* 
    在源串S中查找目标串T，如没有找到则打印出错信息；
    否则，在第一次匹配后请将源串S的匹配部分就地逆置
 */
 
typedef char elementype;
typedef struct node
{
    elementype data;
    struct node * next;
}linkstr;    

linkstr* createstr();
void printstr(linkstr* s);
void reverse(linkstr* s,linkstr* e);
void match(linkstr* s,linkstr* t);

int main()
{
    /*输入源串 */
    linkstr* head = createstr();
    /* 输入目标串 */
    linkstr* t = createstr();
    /* 匹配 */
    match(head,t);
    /* 打印源串 */
    printstr(head);
    return 0;
}

/* create */
linkstr* createstr() 
{
    linkstr* head, *p; 
    /* 头结点 */
    head = p = (linkstr*)malloc(sizeof(linkstr));
    
    printf("input the string
");
    char ch;
    linkstr* tmp = NULL;
    
    while((ch=getchar())!='
')
    {
        tmp = (linkstr*)malloc(sizeof(linkstr));
        tmp->data = ch;
        tmp->next = NULL;

        p->next = tmp;
        p = p->next;
    }

    return head;
}

/* 打印 */
void printstr(linkstr* p) //输出串
{
    p = p->next; /* 有头结点 */
    while(p)
    {
        printf("%c",p->data);
        p = p->next;
    }    
}

/* 逆序 */
void reverse(linkstr* s,linkstr* e)
{
     linkstr* CUR = s->next, *NEW;
     s->next = e;  /* s为逆序字符串的前驱结点 */
     while(CUR!=e)
     {
         NEW = CUR; /* 保存当前指针 */
         CUR = CUR->next; /* 当前指针更新(为新表的前驱) */
         NEW->next = s->next; /* 新结点头插法 */
         s->next = NEW;  /* 新结点插到头结点 */
     }      
}   

/* 匹配 */
void match(linkstr* s,linkstr* t) 
{    
    linkstr* pre = s; /* pre 为逆序需要,保存匹配字符串前驱位置 */
    linkstr* begin = s->next;//begin 源串与目标串比较的位置
    
    linkstr* p, *q;
    p = begin, q = t->next; /* p,q 源串、目标串比较开始位置 */

    while(p&&q)/* 在第一次匹配后 */
    {
        if (p->data==q->data)
        {
            p = p->next;
            q = q->next;
        }
        else
        {            
            pre = begin; /* 匹配字符串前驱位置 */
            begin = begin->next;
            
            p = begin; /* 更新源串 目标串比较位置 */
            q = t->next;
        }        
    }
    if (q==NULL) /* 匹配 */
    {
        reverse(pre,p); /* 匹配部分逆序 */
    }        
    else 
        printf("error!
");
}

朴素模式匹配，链式串的匹配及逆序

View Code

三、广义表也是线性表的一种推广。

　　广义表也是n个数据元素（d1，d2，d3，…， dn）的有限序列，但不同的是，广义表中的di既可以是单个元素，还可以是一个广义表，通常记作：GL=（d1，d2，d3，…，dn）；GL是广义表的名字，通常用大写字母表示；n是广义表的长度；若 di是一个广义表，则称di是广义表GL的子表；在GL中，d1是GL的表头，其余部分组成的表（d2，d3，…， dn）称为GL的表尾；广义表是递归定义的。

　　1、广义表的头尾链表存储结构

表结点可由三个域构成：标志域，指向表头的指针域，指向表尾的指针域；元素结点只需要两个域：标志域和值域；由若干表结点串起来。

头尾链表存储，结构体：

typedef enum {ATOM, LIST} ElemTag; /*ATOM＝0，表示原子；LIST＝1，表示子表*/ 
typedef struct GLNode {
    ElemTag tag; /*标志位tag用来区别原子结点和表结点*/ 
    union {
        AtomType atom; /*原子结点的值域atom*/ 
        struct{ struct GLNode *hp, *tp; } htp; 
        /*表结点的指针域htp，包括表头指针域hp和表尾指针域tp*/ 
    }atom_htp;/*atom  htp的联合体*/ 
} *GList;

头尾链表存储，结构图

　　2、另外，还有一种广义表存储结构，在这种结构中，无论是单元素结点还是子表结点均由三个域构成，只有一个表结点。

结构图