数据结构之非循环单链表

  1 # include <stdio.h>
  2 # include <malloc.h>
  3 # include <stdlib.h>
  4 
  5 typedef struct Node
  6 {
  7     int data; //数据域
  8     struct Node * pNext; //指针域
  9 }NODE, *PNODE; //NODE等价于struct Node    PNODE等价于struct Node *
 10 
 11 PNODE create_list(void);
 12 
 13 void traverse_list(PNODE pHead);
 14 
 15 bool is_empty(PNODE pHead);
 16 
 17 int length_list(PNODE);
 18 
 19 bool insert_list(PNODE,int ,int );
 20 
 21 bool delete_list(PNODE,int ,int * );
 22 
 23 void sort_list(PNODE);
 24 
 25 int main(void )
 26 {
 27     int val;
 28     PNODE pHead=NULL;
 29     pHead=create_list();
 30     traverse_list(pHead);
 31     int len=length_list(pHead);
 32     printf("链表的长度是：%d",len);
 33     printf("
");
 34     if(is_empty(pHead))
 35         printf("链表为空
");
 36     else
 37         printf("链表不空
");
 38     printf("
");
 39     sort_list(pHead);
 40     traverse_list(pHead);
 41     insert_list(pHead,2,22);
 42     printf("插入之后的链表为：");
 43     traverse_list(pHead);
 44     if(delete_list(pHead,4,&val))
 45     {
 46         printf("删除成功，您删除的元素是：%d
",val);
 47     }
 48     else
 49         printf("删除失败，删除元素不存在
");
 50     traverse_list(pHead);
 51     printf("
");
 52     return 0;
 53 } 
 54 PNODE create_list()
 55 {
 56     int len;
 57     int i;
 58     int val;
 59     PNODE pHead =(PNODE)malloc(sizeof(NODE));
 60     if(pHead==NULL)
 61     {
 62         printf("分配失败
");
 63         exit(-1);
 64     }
 65     PNODE ptail=pHead;
 66     ptail->pNext=NULL;//定义一个临时的指针变量，能够是ptail总是指向为节点的后面
 67 
 68     printf("请输入链表的数据元素的长度：
");
 69     scanf("%d",&len);
 70     for(i=0;i<len;i+=1)
 71     {
 72         PNODE pnew=(PNODE)malloc(sizeof(NODE));
 73         if(NULL==pnew)
 74         {
 75             printf("分配失败
");
 76             exit(-1);
 77         }
 78         printf("请输入地%d个数据元素：
",i+1);
 79         scanf("%d",&val);
 80         pnew->data=val;
 81         ptail->pNext=pnew;
 82         pnew->pNext=NULL;
 83         ptail=pnew;        
 84     }
 85     return pHead;
 86 }
 87 
 88 void traverse_list(PNODE pHead)
 89 {
 90     PNODE p=pHead->pNext;
 91     while(p!=NULL)
 92     {
 93         printf("%d ",p->data);
 94         p=p->pNext;
 95     }
 96     return;
 97 }
 98 
 99 bool is_empty(PNODE pHead)
100 {
101      if(pHead->pNext==NULL)
102      {
103          return true;
104      }
105      else
106          return false;
107 }
108 
109 int length_list(PNODE pHead)
110 {
111     PNODE p =pHead ->pNext;
112     int len=0;
113     while(p!=NULL)
114     {
115         len+=1;
116         p=p->pNext;
117     }
118     return len;
119 }
120 
121 void sort_list(PNODE pHead)//对数据项进行排序
122 {
123     int i,j,t;
124     PNODE p,q;
125     int len=length_list(pHead);
126     for(i=0,p=pHead->pNext;i<len-1;i+=1,p=p->pNext)
127         for(j=i+1,q=p->pNext;j<len;j+=1,q=q->pNext)
128         {
129             if(p->data>q->data)
130             {
131                 t=p->data;
132                 p->data=q->data;
133                 q->data=t;
134             }
135         }
136     return;
137 }
138 
139 //在phead指向链表的第pos个节点的前面插入一个新的结点，该节点的值是val
140 //并且，pos的值是从1开始的
141 bool insert_list(PNODE pHead,int pos ,int val )
142 {
143      int i=0;
144      PNODE p=pHead;
145      while(NULL!=p&&i<pos-1)
146      {
147          p=p->pNext;
148          i+=1;
149      }
150      if(NULL==p||i>pos-1)
151          return false;
152      PNODE pnew=(PNODE)malloc(sizeof(NODE));
153      if(NULL==pnew)
154      {
155          printf("动态分配内存失败");
156          exit(-1);
157      }
158      pnew->data=val;//将要插入的val值付给pnew的data
159      PNODE q=p->pNext;
160      p->pNext=pnew;
161      pnew->pNext=q;
162 
163      return true;
164 }
165 
166 bool delete_list(PNODE pHead,int pos ,int *pval )
167 {
168      int i=0;
169      PNODE p=pHead;
170      while(NULL!=p->pNext&&i<pos-1)
171      {
172          p=p->pNext;
173          i+=1;
174      }
175      if(NULL==p->pNext||i>pos-1)
176          return false;
177      PNODE q=p->pNext;
178      *pval=q->data;
179      
180      //删除p节点后面的节点
181      p->pNext=p->pNext->pNext;
182      free(q);
183      q=NULL;
184      
185 
186      return true;
187 }