数据结构（严版）课本代码重敲——第二章

  1 #include <iostream>
  2 #include <string.h>
  3 #include <stdio.h>
  4 #include <stdlib.h>
  5 #define dataSize 20
  6 #define ERROR -1
  7 using namespace std;
  8 /*
  9     题目：数据结构 cha2 线性表
 10     内容：1. 顺序表的操作
 11     日期：2018/3/9
 12     时间：tomato * 2
 13     笔记：1. 线性表包括顺序表和链表
 14     2. 顺序表是逻辑和存储结构均为线性连续的数组形式，一般用数组表示
 15     3.链表分为单链表和双链表，包括带头结点和不带头结点两种类型，也包括循环和非循环两种类型
 16     还有一种特殊的“静态链表”
 17 */
 18 /* 顺序表的定义方式
 19     注意：typedef的含义是给这个结构体起的名字叫做Sqlist,是一种用户自定义的数据类型
 20     而平时编程中struct student {}stu[20];则是C++中的简略写法，stu[20]即为创建的
 21     数据类型为Student的数组变量
 22 */
 23 typedef struct
 24 {
 25     int data[dataSize];
 26     int length;
 27 }Sqlist;
 28 
 29 
 30 typedef int Elemtype;
 31 
 32 
 33 /* (1)以下为顺序表的基本操作
 34     1. 初始化
 35     2. 按元素值的查找
 36     3. 求指定位置元素
 37     4. 插入元素
 38     5. 删除元素
 39     笔记：1.是否用&取决于改结构体的内容
 40 */
 41 void initSqlist(Sqlist &l)
 42 {
 43     l.length = 0;
 44 }
 45 int findElem(Sqlist l,Elemtype x)
 46 {
 47     for (int i=0;i<l.length;i++)
 48     {
 49         if (l.data[i] == x)
 50             return i;
 51     }
 52     return ERROR;
 53 }
 54 Elemtype getElem(Sqlist l, int loc)
 55 {
 56     if (loc < 0 || loc > l.length-1)
 57         return ERROR;
 58     return l.data[loc];
 59 }
 60 void insertSqlist(Sqlist &l,Elemtype x,int loc)
 61 {
 62     if (loc < 0 || loc >l.length-1)
 63         cout<<"error";
 64     for (int i=l.length-1 ; i >= loc ; i--  )
 65     {
 66         l.data[i+1] = l.data[i];
 67     }
 68     l.data[loc] = x;
 69     l.length++; // ★★★ 勿忘！
 70 }
 71 Elemtype deleteSqlist(Sqlist &l,int loc,Elemtype &x)
 72 {
 73     if (loc<0||loc>l.length-1)
 74         {cout << "error";return 0;}
 75     x = l.data[loc];
 76     for (int i=loc;i<l.length-1;i++)
 77     {
 78         l.data[i] = l.data[i+1];
 79     }
 80     l.length -- ;
 81     return x;
 82 }
 83 // 单链表结点定义
 84 typedef int Elemtype;
 85 typedef struct LNode
 86 {
 87     Elemtype data;
 88     struct LNode *next;
 89 }LNode;
 90 
 91 /*
 92     (2)单链表的操作
 93     1. 创建单链表 尾插法和头插法
 94     2. 归并单链表 递增和递减（头插法）
 95     3. 查找单链表
 96     4. 插入单链表
 97     5. 删除
 98     6. 打印链表内容
 99     7. 查找x并删除
100 */
101 // 头插法
102 void createLNode(LNode *&h,int n)
103 {
104     // 1. 创建头结点
105     h = (LNode *)malloc(sizeof(LNode));
106     h->next = NULL;
107     Elemtype x;
108     cout<<"输入线性表数据"<<endl;
109     LNode *q;
110     q = h;
111     for(int i=0;i<n;i++)
112     {
113         cin >> x;
114         q = (LNode *)malloc(sizeof(LNode));
115         q->data = x;
116         q->next = h->next;
117         h->next = q;
118     }
119 
120 }
121 // 尾插法
122 void createLNodeH(LNode *&h,int n)
123 {
124     h = (LNode *)malloc(sizeof(LNode));
125     h->next = NULL;
126     LNode *p,*q;
127     q = h;
128     int x;
129     cout <<"数据："<<endl;
130     for (int i=0;i<n;i++)
131     {
132         cin >> x;
133         p = (LNode *) malloc(sizeof(LNode));
134         p->data = x;
135         q->next = p;
136         q = p;
137     }
138     p->next = NULL; // 最后赋值即可
139 
140 }
141 void print(LNode *h)
142 {
143     LNode *t = h;
144     while (t->next!=NULL)
145     {
146         t = t->next;
147         cout<<t->data<<‘ ‘;
148     }
149     cout << endl;
150 }
151 void mergeLNode(LNode *&a,LNode *&b,LNode *&c)
152 {
153     LNode *pa,*pb,*pc;
154     pa = a->next;pb=b->next;
155     pc = (LNode *)malloc(sizeof(LNode));
156     c = pc ;
157     while (pa!=NULL && pb!=NULL)
158     {
159         cout <<"test"<<endl;
160         if (pa->data >= pb->data)
161         {
162             pc->next = pb;
163             pb = pb->next;
164             pc = pc->next;
165         }
166         else
167         {
168             pc->next = pa;
169             pa = pa->next;
170             pc = pc->next;
171         }
172     }
173     pc->next = NULL;
174     if (pa!=NULL)
175     {
176         pc->next = pa;
177     }
178     if (pb!=NULL)
179     {
180         pc->next = pb;
181     }
182 
183 }
184 void merge_2(LNode *&a,LNode *&b,LNode *&c)
185 {
186     LNode *pa,*pb,*pc;
187     pa = a->next; pb = b->next;
188     c = (LNode *)malloc(sizeof(LNode));
189     pc = c;
190 
191     while (pa!=NULL && pb!=NULL)
192     {
193         if (pa->data >= pb->data)
194         {
195             pc = pb;
196             pb = pb->next;
197             pc -> next = c->next;
198             c->next = pc;
199         }
200         else
201         {
202             pc = pa;
203             pa = pa->next;
204             pc -> next = c->next;
205             c->next = pc;
206         }
207     }
208     while (pa!=NULL)
209     {
210         pc = pa;
211         pa = pa->next;
212         pc -> next = c->next;
213         c->next = pc;
214     }
215     while (pb!=NULL)
216     {
217         pc = pb;
218         pb = pb->next;
219         pc -> next = c->next;
220         c->next = pc;
221     }
222 }
223 
224 int findAndDelete(LNode *l,Elemtype x)
225 {
226     LNode *p = l,*q;
227 
228     while (p->next!=NULL)
229     {
230        if (p->next->data == x)
231        {
232            q = p->next ;
233            p->next = q->next;
234            return 1;
235        }
236        p = p->next;
237     }
238     return 0;
239 }
240 // 双链表结点定义
241 typedef struct DLNode
242 {
243     Elemtype data;
244     struct DLNode *prior;
245     struct DLNode *next;
246 }DLNode;
247 
248 /*
249     1.双链表的建立
250     2. 查找结点
251     3. 插入结点，在p之后
252 */
253 void createDLNode(DLNode *&dl,int n)
254 {
255     dl = (DLNode *)malloc(sizeof(DLNode));
256     dl ->prior = NULL;
257     DLNode *p,*q;
258     p = dl;
259     cout<<"data:"<<endl;
260     int x;
261     for (int i=0;i<n;i++)
262     {
263         q = (DLNode *)malloc(sizeof(DLNode));
264         cin >> x;
265         q->data = x;
266         p->next = q;
267         q->prior = p;
268         p = q;
269     }
270     p->next = NULL;
271 
272 }
273 
274 int main()
275 {
276     DLNode *dl;
277     int n;
278     cout<<"数据个数n："<<endl;
279     cin>>n;
280     createDLNode(dl,n);
281     print(dl);
282     return 0;
283 }