数据结构：链表插入和删除算法的演示

87 阅读 0 评论 58 点赞

我是靠谱客的博主谦让水蜜桃，最近开发中收集的这篇文章主要介绍数据结构：链表插入和删除算法的演示，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

  1 # include <stdio.h>
  2 # include <malloc.h>
  3 # include <stdlib.h>
  4
  5 typedef struct Node   // 要理解typedef的用法
  6 {
  7      int data;
  8      struct Node * pNext;
  9 }NODE, * PNODE;
10 PNODE creat( void);
11 void traverse(PNODE pHead);    // 注意函数的返回值类型
12 bool empty(PNODE pHead);
13 int length(PNODE);
14 bool insert(PNODE, int, int);
15 bool delet(PNODE, int, int *);
16 void sort(PNODE);
17
18 int main( void)
19 {
20     PNODE pHead = NULL;
21      int len;
22      int val;
23     pHead = creat();
24     traverse(pHead);
25      if(empty(pHead))
26         printf( " 空n ");
27      else
28         printf( " 不空n ");
29     len = length(pHead);
30     printf( " 链表的长度是%dn ",len);
31     sort(pHead);
32     traverse(pHead);
33     insert(pHead, 3, 31);
34     traverse(pHead);
35      if(delet(pHead, 3,&val))
36     {
37         printf( " 删除成功，您删除的元素为：%d!n ",val);
38     }
39      else
40     {
41         printf( " 删除失败~ ");
42     }
43     traverse(pHead);
44
45      return 0;
46
47 }
48 PNODE creat( void)
49 {
50      int len;
51      int i;
52      int val;
53     PNODE pHead = (PNODE)malloc( sizeof(NODE));
54      if(NULL == pHead)
55     {
56         printf( " 分配失败，程序终止 ");
57         exit(- 1);
58     }
59     PNODE pTail = pHead;
60     pTail->pNext = NULL;
61     printf( " 请输入链表节点长度：len= ");
62     scanf( " %d ",&len);
63      for(i= 0;i<len;i++)
64     {
65         printf( " 请输入第%d个值 ",i+ 1);
66         scanf( " %d ",&val);
67         PNODE pNew = (PNODE)malloc( sizeof(NODE));
68
69              if(NULL == pNew)
70             {
71                 printf( " 分配失败，程序终止 ");
72                 exit(- 1);
73             }
74         pNew->data = val;
75         pTail->pNext = pNew;
76         pNew->pNext= NULL;
77         pTail = pNew;     // 算法要理解，可借助图形加上理解
78
79     }
80      return pHead; // 返回值
81
82 }
83
84 void traverse(PNODE pHead) // 遍历
85 {
86     PNODE p = pHead->pNext;
87
88      while(NULL != p)
89     {
90         printf( " %d ",p->data);
91         p = p->pNext;    // 移到下一个节点
92
93     }
94     printf( " n ");
95
96 }
97 bool empty(PNODE pHead) // 判断是否为空
98 {
99      if(NULL == pHead->pNext)
100          return true;
101      else
102          return false;
103 }
104 int length(PNODE pHead)
105 {
106     PNODE p = pHead->pNext;
107      int len = 0;
108
109      while(NULL != p)
110     {
111         ++len;
112         p = p->pNext;
113     }
114      return len;
115
116 }
117 void sort(PNODE pHead) // 排序
118 {
119      int i,j,t;
120      int len;
121     PNODE p,q;
122     len = length(pHead);
123      for(i= 0,p=pHead->pNext ;i<len- 1;i++ ,p=p->pNext)
124     {
125          for(j=i+ 1,q=p->pNext;j<len;j++,q=q->pNext)
126         {
127              if(q->data > p->data)
128             {
129             t = q->data;
130             q->data = p->data;
131             p->data=t;
132             }
133
134         }
135     }
136      return;
137 }
138 bool insert(PNODE pHead, int pos, int val) // 插入
139 {
140      int i = 0;
141     PNODE p = pHead;
142
143      while(NULL != p && i<pos- 1)
144     {
145         p = p->pNext;
146         i++;
147     }
148      if(i>pos- 1 || NULL==p)
149          return false;
150     PNODE pNew = (PNODE)malloc( sizeof(NODE));
151      if(NULL == pNew)
152     {
153         printf( " 动态内存分配失败n ");
154         exit(- 1);
155     }
156     pNew->data = val;
157     PNODE q=p->pNext;
158     p->pNext = pNew;
159     pNew->pNext=q;
160
161      return true;
162 }
163 bool delet(PNODE pHead, int pos, int * pVal) // 删除
164 {
165      int i = 0;
166     PNODE p = pHead;
167
168      while(NULL != p->pNext && i<pos- 1)
169     {
170         p = p->pNext;
171         i++;
172     }
173      if(i>pos- 1 || NULL==p->pNext)
174          return false;
175     PNODE q = p->pNext;
176     *pVal = q->data;
177     p->pNext = p->pNext->pNext;
178     free(q);
179     q=NULL;
180      return true;
181
182 }
183 /*
184 =============================
185 请输入链表节点长度：len= 4
186 请输入第1个值23
187 请输入第2个值54
188 请输入第3个值12
189 请输入第4个值33
190 23 54 12 33
191 不空
192 链表的长度是4
193 54 33 23 12
194 54 33 31 23 12
195 删除成功，您删除的元素为：31!
196 54 33 23 12
197 Press any key to continue
198 =============================
199 */

转载于:https://www.cnblogs.com/jssong20000/archive/2012/11/07/2759370.html