链表的各种操作

  1 #include<stdio.h>
  2 #include<stdlib.h>
  3 #define N  10     //结点个数
  4 typedef struct LNode
  5 {
  6     int data;
  7     struct LNode *next;
  8 }LNode,*LinkList;
  9 
 10 LinkList creat_Linklist()  //已知节点个数，并且不带头结点
 11 {
 12      LNode   *head=NULL,*s,*rear=NULL;  //尾插法需要用到尾指针，rear是尾指针
 13      for(int i=1;i<=N;i++)
 14      {
 15          s=(LinkList)malloc(sizeof( LNode));
 16          scanf("%d",&s->data);
 17          s->next=NULL;    //把当前结点next置空NULL
 18          if(i==1)    //用来标记插入的节点是否为第一个节点，是的话就让头结点head指向第一个节点
 19              head=s;
 20          else    
 21              rear->next=s;   //不是头结点的话就让上一个节点的next指向当前结点
 22          rear=s;   //尾指针rear指向当前节点
 23      }
 24      return head;   //返回头指针
 25 }
 26 int LinkList_length(LinkList head)  //q求链表长度
 27 {
 28  
 29     int count=0;
 30     LNode * p=NULL;
 31     p=head;
 32     while(p!=NULL)
 33     {
 34          p=p->next;
 35          count++;
 36     }
 37     return count;
 38 }
 39 LinkList Clear_LinkList(LinkList head)  //用于清空没有头结点的链表，只是清空，没有释放掉，直接把头指针置空NULL即可
 40 {  
 41          if(head==NULL) 
 42          {
 43              printf("链表为空\n ");
 44              exit(-1);     
 45          }
 46          return NULL;  
 47 }  
 48 int EmptyList(LinkList head)//用于判断没有头结点的情况；空表返回1，非空返回0
 49 {
 50        if(head==NULL)
 51             return 1;
 52        else
 53             return 0;
 54 }
 55 LinkList Search(LinkList head,int x)  //查找链表中的某一数据，查找成功返回一个指向它的指针，失败返回NULL
 56 {
 57          LNode *p;
 58          p=head;
 59          while(p)
 60          {      
 61             if(p->data!= x)
 62                p=p->next;
 63             else
 64                break;
 65          }
 66          return p;
 67 }
 68 void Print_LinkList(LinkList head)  //打印链表
 69 {
 70          LNode *p;
 71          p=head;
 72          while(p!= NULL)
 73          {          
 74               printf("%d ",p->data);  
 75               p=p->next;
 76          }
 77 }
 78 LinkList reverseList(LinkList head)  //翻转链表
 79 {
 80             LNode *pre,*cur,*net;
 81             pre=head;
 82             cur=pre->next;
 83             while(cur!= NULL)  //当前指针cur非空
 84             {
 85                  net=cur->next;
 86                  cur->next=pre;
 87                  pre=cur;
 88                  cur=net;
 89             }
 90             head->next=NULL;  //将原来链表中第一个结点的next置空NULL
 91             head=pre;  //此时pre指向最后一个结点
 92             return  head;
 93 }
 94 LinkList DeleteList(LinkList head,int i) //删除序号为i的结点，结点序号从1开始
 95 {
 96          int j=1;
 97          LNode *p,*q;
 98          p=head;
 99          while(p->next!=NULL&&j<i-1)
100          {
101                p=p->next; 
102                j++;      //查找待删除结点的前一个节点
103          }
104          if ( !(p->next) || j>i-1) //1号位置无法删除
105          {
106              printf("删除位置错误");
107              return  0;
108          }
109          q=p->next;  //q指向待删除结点
110          p->next=q->next;  //跳过待删除结点，
111          free(q);    //释放待删除结点
112          return  head;
113 }
114 LinkList InsertList(LinkList head,int i,int e)//在序号为i的结点位置插入e
115 {    
116          int j=1;
117          LNode *p,*q;
118          p=head;
119          while(p&&j<i-1) //查找待插入位置的前一个位置
120          {
121                p=p->next;
122                j++;
123          }
124          if(!p || j>i-1) //1号位置无法插入
125          {
126              printf("插入位置错误");
127              return  0;
128          }
129          q=(LinkList)malloc(sizeof(LNode)); //为新结点开辟空间
130          q->data=e;
131          q->next=p->next;
132          p->next=q;
133          return  head;
134 }
135 int main()
136 {
137     LinkList p;
138     p=creat_Linklist();
139     printf("链表中的数据为:");
140     Print_LinkList (p);
141     printf("\n链表长度:%d\n",LinkList_length(p));
142     printf("翻转后的链表为:");
143     p=reverseList (p);   //翻转链表，返回头指针
144     Print_LinkList (p);
145     printf("\n删除序号为3的结点后，链表中的元素为：");
146     p=DeleteList(p,3);   //删除序号为3的结点，序号从1开始
147     Print_LinkList(p);
148     printf("\n删除序号为3的结点后,链表长度:%d",LinkList_length(p));
149     printf("\n在序号为3的结点位置插入80后，链表中的元素为：");
150     p=InsertList(p,3,80);
151     Print_LinkList(p);
152     printf("\n在序号为3的结点位置插入80后，链表长度为：%d\n",LinkList_length(p));
153     LinkList s;
154     s=Search(p,80);//在链表里查找某一数据
155     if(s==NULL)
156         printf("在链表查找失败\n");
157     else
158         printf("在链表查找成功，结果为：%d\n",*s);
159     printf("结果为1表示链表为空，为0表示链表非空：%d\n",EmptyList(p));
160     p=Clear_LinkList(p); //清空链表
161     printf("结果为1表示链表为空，为0表示链表非空：%d\n",EmptyList(p));
162     printf("清空链表后，链表长度为：%d\n",LinkList_length(p));
163     return 0;
164}

 1 void  Destroy_LinkList (LinkList  head)
 2 {
 3          LNode *p,*q;
 4          p=head;
 5          while(p  != NULL)
 6          {    q=p;
 7                p=p->next;
 8                free(q);
 9          }
10 }