数据结构算法C语言实现（二）---2.3线性表的链式表示和实现之单链表
一.简述
【暂无】
二.头文件
1 #ifndef _2_3_part1_H_
2 #define _2_3_part1_H_
3 //2_3_part1.h
4 /**
5 author:zhaoyu
6 email:zhaoyu1995.com@gmail.com
7 date:2016-6-4
8 note:realize my textbook <<数据结构（C语言版）>>
9 */
10 //----线性表的单链表存储结构----
11 /**
12 My Code
13 to make the paragram run correctlly
14 */
15 #define ElemType int
16 typedef struct LNode{
17 ElemType data;
18 struct LNode *next;
19 }LNode, *LinkList;
20 /**
21 algorithm 2.8
22 */
23 Status GetElem_L(LinkList L, int i, ElemType &e)
24 {
25 //L为带头结点的单链表的头指针
26 //当第i个元素存在时，其值赋给e并返回OK，否则返回ERROR
27 LinkList p = L->next;
28 int j = 1;//初始化，p指向第一个节点，j为计数器
29 while (p && j<i)
30 {//顺指针向后查找，直到p指向第i个元素或p为空
31 p = p->next;
32 ++j;
33 }
34 if (!p || j > i)
35 {//第i个元素不存在
36 return ERROR;
37 }
38 e = p->data;//取第i个元素
39 return OK;
40 }//GetElem_L
41 //关于指针的引用
42 /**
43 algorithm 2.9
44 */
45 Status ListInsert_L(LinkList &L, int i, ElemType e)
46 {
47 //在带头结点的单链线性表L中第i个位置之前插入元素
48 LinkList p = L;
49 int j = 0;
50 while (p && j < i-1)
51 {//寻找第i-1个节点
52 p = p->next;
53 ++j;
54 }
55 if (!p || j>i-1)
56 {//i小于 1 或大于表长加 1
57 return ERROR;
58 }
59 LinkList s = (LinkList)malloc(sizeof(LNode));
60 s->data = e;//插入 L 中
61 s->next = p->next;//注意顺序
62 p->next = s;
63 return OK;
64 }//ListInsert_L
65
66 /**
67 algorithm 2.10
68 */
69 Status ListDelete_L(LinkList &L, int i, ElemType &e)
70 {
71 //在带头结点的单链线性表L中，删除第 i 个节点，并由 e 返回其值
72 LinkList p = L;
73 int j = 0;
74 while (p->next && j < i-1)
75 {//寻找第 i 个节点，并另 p 指向其前驱
76 p = p->next;
77 ++j;
78 }
79 if (!(p->next) || j > i-1)
80 {//删除位置不合理
81 return ERROR;
82 }
83 LinkList q = p->next;
84 p->next = q->next;//删除并释放节点
85 e = q->data;
86 free(q);
87 return OK;
88 }//ListDelete_L
89 /**
90 algorithm 2.11
91 从表尾到表头逆向建立单链表的算法
92 */
93 void CreateList_L(LinkList &L, int n)
94 {
95 //逆位序输入 n 个元素的值，建立带表头节点的单链线性表 L
96 L = (LinkList)malloc(sizeof(LNode));
97 L->next = NULL;//先建立一个带头结点的单链表
98 for (int i = n; i > 0; i--)
99 {
100 LinkList p = (LinkList)malloc(sizeof(LNode));//生成新节点
101 scanf("%d", &p->data);//输入元素值
102 p->next = L->next;
103 L->next = p;//插入到表头
104 }
105 }//CreateList_L
106 /**
107 algorithm 2.12
108 */
109 void MergeList_L(LinkList &La, LinkList &Lb, LinkList &Lc)
110 {
111 //已知单链线性表 La 和 Lb 的元素按值非递减排列
112 //归并 La 和 Lb 得到新的单链线性表 Lc，Lc的元素也按值非递减排列
113 LinkList pa = La->next, pb = Lb->next;
114 LinkList pc = Lc = La;//用 La 的头结点作为 Lc 的头结点
115 while (pa && pb)
116 {
117 if (pa->data <= pb->data)
118 {
119 pc->next = pa;
120 pc = pa;
121 pa = pa->next;
122 }
123 else
124 {
125 pc->next = pb;
126 pc = pb;
127 pb = pb->next;
128 }
129 }
130 pc->next = pa ? pa : pb;//插入剩余节点
131 free(Lb);
132 }//MergeList_L
133
134 /**
135 My Code
136 */
137 void PrintList(LinkList L)
138 {
139 LinkList p = L->next;
140 while (p != NULL)
141 {
142 printf("%d\t", p->data);
143 p = p->next;
144 }
145 printf("\n");
146 }
147 #endif
View Code
三.CPP文件
1 //2_3_part1.cpp
2 /**
3 author:zhaoyu
4 email:zhaoyu1995.com@gmail.com
5 date:2016-6-4
6 note:realize my textbook <<数据结构（C语言版）>>
7 */
8 #include "head.h"
9 #include "2_3_part1.h"
10 int main(int argc, char const *argv[])
11 {
12 LinkList La, Lb, Lc;
13 //逆序建表
14 printf("Create ListA\n");
15 CreateList_L(La, 4);
16 printf("Create ListB\n");
17 CreateList_L(Lb, 6);
18 printf("Print ListA\n");
19 PrintList(La);
20 printf("Print ListB\n");
21 PrintList(Lb);
22 printf("Insert 7 at location 4 In ListA\n");
23 ListInsert_L(La, 4, 7);
24 PrintList(La);
25 printf("Delete 7 at location 3 In ListB\n");
26 int temp;
27 ListDelete_L(Lb, 3, temp);
28 PrintList(Lb);
29 printf("%d is deleted\n", temp);
30 printf("Merge ListA and ListB\n");
31 MergeList_L(La, Lb, Lc);
32 PrintList(Lc);
33 printf("Get element at location 1 2 3 in ListC\n");
34 int e1, e2, e3;
35 GetElem_L(Lc,1,e1);
36 GetElem_L(Lc,2,e2);
37 GetElem_L(Lc,3,e3);
38 printf("%d\t%d\t%d\n", e1, e2, e3);
39 return 0;
40 }
View Code
四.测试
