【1】线性表的链式存储
线性表的顺序存储结构特点：
逻辑关系上相邻的两个元素在物理位置上也相邻；
可以随机存取任一元素，它的存储位置可用一个简单直观的公式表示。
然而，从另一个角度来看，这个优点也表明了这种存储结构的弱点：
在做插入或删除操作时，需要移动大量的元素。
线性表的链式存储不要求逻辑上相邻的元素在物理位置上也相邻。
因此，它没有顺序存储结构所具有的弱点，但同时也失去随机存取的优点。
另外一点：
链式存储的存储空间采用动态分配，不会存在分配不够用或者浪费的情况。
【2】链式存储结构
链式存储结构如下图：
【3】单链表的实现
1. list.h 头文件
1 #ifndef _STDAFX_H 2 #define _STDAFX_H 3 4 #include5 #include 6 #include 7 8 typedef enum { ERROR = 0, OK} Status; 9 10 typedef int ElemType;11 12 typedef struct _Node13 {14 ElemType data;15 struct _Node *next;16 } Node, *PNode, *Position;17 18 typedef struct 19 {20 PNode head, tail;21 size_t size;22 } List, *PList;23 24 25 PList InitList();26 void FreeNode(PNode p);27 PNode BuyNode(ElemType x, PNode pN = NULL);28 29 void Print_List(PList _list);30 void DestroyList(PList _list);31 void ClearList(PList _list);32 33 void Push_Back(PList _list, ElemType x);34 void Push_Front(PList _list, ElemType x);35 void Pop_Back(PList _list);36 void Pop_Front(PList _list);37 38 PNode FindPreValue(PList _list, ElemType x);39 PNode FindPos(PList _list, int pos);40 41 Status Remove(PList _list, ElemType x);42 Status RemoveAll(PList _list, ElemType x);43 44 Status Erase(PList _list, size_t pos);45 46 Status Insert(PList _list, int pos, ElemType x);47 48 void Sort(PList _list);49 void Reverse(PList _list);50 void Merge(PList _list, PList _list1, PList _list2);51 void Link(PList _list, PList _list1);52 53 size_t Size(PList _list);54 55 #endif
2. list.cpp 实现文件
1 #include "List.h" 2 using namespace std; 3 4 // 购买节点 5 PNode BuyNode(ElemType x, PNode n) 6 { 7 PNode s = (PNode)malloc(sizeof(Node)); 8 assert(NULL != s); //断言函数 9 s->data = x; 10 s->next = n; 11 return s; 12 } 13 // 释放节点 14 void FreeNode(PNode p) 15 { 16 free(p); 17 p = NULL; 18 } 19 // 初始化链表 20 PList InitList() 21 { 22 PList p = (PList)malloc(sizeof(List)); 23 assert(p != NULL); 24 p->size = 0; 25 p->head = p->tail = BuyNode(0, NULL); //表明是有头结点的单链表 26 return p; 27 } 28 // 后面插入数据 29 void Push_Back(PList _list, ElemType x) 30 { 31 _list->tail = _list->tail->next = BuyNode(x, NULL); 32 _list->size += 1; 33 } 34 // 前面插入数据 35 void Push_Front(PList _list, ElemType x) 36 { 37 PNode s =_list->head->next = BuyNode(x, _list->head->next); 38 if (NULL == s->next) 39 { 40 _list->tail = s; 41 } 42 _list->size += 1; 43 } 44 // 打印链表 45 void Print_List(PList _list) 46 { 47 PNode p = _list->head->next; 48 cout << "元素个数: " << _list->size << endl; 49 while (p != NULL) 50 { 51 cout << p->data << " "; 52 p = p->next; 53 } 54 cout << endl; 55 } 56 // 清空链表 57 void ClearList(PList _list) 58 { 59 PNode q = NULL; 60 PNode s = _list->head->next; 61 while (s != NULL) 62 { 63 q = s; 64 s = s->next; 65 free(q); //FreeNode(q); 66 } 67 _list->size = 0; 68 _list->head->next = NULL; 69 _list->tail = _list->head; 70 } 71 // 摧毁链表 72 void DestroyList(PList _list) 73 { 74 ClearList(_list); 75 free(_list->head); 76 free(_list); 77 } 78 // 后面弹出 79 void Pop_Back(PList _list) 80 { 81 PNode p = _list->head; 82 //循环定位找最后节点的前驱 83 while (p->next != NULL && p->next->next != NULL) 84 { 85 p = p->next; 86 } 87 88 if (p->next != NULL) 89 { 90 PNode q = p->next; 91 p->next = NULL; 92 _list->tail = p; 93 free(q); //FreeNode(q); 94 _list->size -= 1; 95 } 96 } 97 // 前面弹出 98 void Pop_Front(PList _list) 99 {100 if (_list->head->next != NULL)101 {102 PNode q = _list->head->next;103 _list->head->next = q->next;104 free(q); // FreeNode(p);105 _list->size -= 1;106 // 链表仅有一个元素107 if (NULL == _list->head->next)108 {109 _list->tail = _list->head;110 }111 }112 } 113 // 查找某值前驱114 PNode FindPreValue(PList _list, ElemType x)115 {116 PNode p = _list->head;117 while (p->next != NULL && p->next->data != x)118 { 119 p = p->next;120 }121 122 if (NULL == p->next)123 {124 p = NULL;125 }126 127 return p;128 }129 // 删除某值130 Status Remove(PList _list, ElemType x)131 {132 PNode p = FindPreValue(_list, x); //找到前驱133 if (NULL == p) 134 {135 return ERROR;136 }137 138 PNode q = p->next;139 p->next = q->next;140 141 _list->size -= 1;142 return OK;143 }144 // 找某位置的节点145 PNode FindPos(PList _list, int pos)146 {147 if (pos < -1) 148 return NULL;149 if (-1 == pos) 150 return _list->head;151 152 int j = 0;153 PNode p = _list->head->next;154 while (j < pos && p != NULL)155 {156 p = p->next;157 ++j;158 }159 return p;160 }161 // 删除某位置的值162 Status Erase(PList _list, size_t pos)163 {164 if (pos >= _list->size)165 {166 cout<<"输入位置有误！！！"< next == NULL) //前者说明空链表//后者说明末节点170 {171 return ERROR;172 }173 174 PNode q = p->next;175 p->next = q->next;176 177 if (p->next == NULL)178 {179 _list->tail = p;180 }181 FreeNode(q);182 --_list->size;183 return OK;184 }185 // 按位置插入数据186 Status Insert(PList _list, int pos, ElemType x)187 {188 PNode p = FindPos(_list, pos-1);189 if (NULL == p)190 {191 return ERROR;192 }193 p->next = BuyNode(x, p->next);//顺利衔接194 PNode s = p->next;195 if (s->next == NULL)196 {197 _list->tail = s;198 }199 ++_list->size;200 return OK;201 }202 // 逆置链表203 void Reverse(PList _list)204 {205 if (_list->size >= 2)206 {207 PNode s = _list->head->next;208 _list->tail = s;209 PNode p = s->next;210 s->next = NULL;211 while (p != NULL)212 {213 s = p;214 p = p->next;215 s->next = _list->head->next;216 _list->head->next = s;217 }218 }219 }220 // 合并221 void Merge(PList _list, PList _list1, PList _list2)222 {223 PNode r = _list->head;224 PNode p1 = _list1->head->next;225 PNode p2 = _list2->head->next;226 // 执行合并227 while (p1 != NULL && p2 != NULL)228 {229 if (p1->data <= p2->data)230 {231 r->next = p1;232 p1 = p1->next;233 }234 else235 {236 r->next = p2;237 p2 = p2->next;238 }239 r = r->next;240 }241 // _list2先合并完成242 if (p1 != NULL)243 {244 r->next = p1;245 _list->tail = _list1->tail;246 }247 // _list1先合并完成248 if (p2 != NULL)249 {250 r->next = p2;251 _list->tail = _list2->tail;252 }253 // 合并数量254 _list->size = _list1->size + _list2->size;255 // 收尾256 _list1->head->next = NULL;257 _list1->tail = _list1->head;258 _list1->size = 0;259 260 _list2->head->next = NULL;261 _list2->tail = _list2->head;262 _list2->size = 0;263 }264 //连接265 void Link(PList _list, PList _list1)266 {267 _list->tail->next = _list1->head->next;268 _list->tail = _list1->tail;269 _list->size += _list1->size;270 271 _list1->head->next = NULL;272 _list1->tail = _list1->head;273 _list1->size = 0;274 }275 276 /*277 * 逆置方式2278 void Reverse(PList _list)279 {280 PNode r = _list->head->next;281 PNode s = r->next;282 PNode p = s->next;283 r->next = NULL;284 _list->tail = r;285 while (p != NULL)286 {287 s->next = r;288 r = s;289 s = p;290 p = p->next;291 }292 s->next = r;293 _list->head->next = s;294 }295 */ 3. listmain.cpp 测试文件
1 #include "List.h" 2 using namespace std; 3 4 #define UM_QUIT 0 5 #define UM_INPUTR 1 6 #define UM_INPUTH 2 7 #define UM_PRINT 3 8 #define UM_ERASE 4 9 #define UM_REMOVE 5 10 #define UM_POPFRONT 6 11 #define UM_POPBACK 7 12 #define UM_INSERT 8 13 #define UM_REVERSE 9 14 #define UM_MERGE 10 15 #define UM_LINK 11 16 17 #define ListNum0 0 18 #define ListNum1 1 19 #define ListNum2 2 20 21 void main() 22 { 23 PList mylist, mylist1, mylist2; 24 int select = 1, pos = 0, num = 0; 25 ElemType item; 26 mylist = InitList(); 27 mylist1 = InitList(); 28 mylist2 = InitList(); 29 while (select != 0) 30 { 31 cout << "\t\t*********************菜单********************* " << endl; 32 cout << "\t\t** 1.输入数据r 2.输入数据h " << endl; 33 cout << "\t\t** 3.打印数据 4.位置删除 " << endl; 34 cout << "\t\t** 5.删除某值 6.前面弹出 " << endl; 35 cout << "\t\t** 7.后面弹出 8.位置插入 " << endl; 36 cout << "\t\t** 9.逆置链表 10.合并链表 " << endl; 37 cout << "\t\t** 11.连接链表 0.退出 " << endl; 38 cout << "\t\t**********************************************\t\t\t\t" << endl; 39 cout << "请选择" << endl; 40 cin >> select; 41 switch (select) 42 { 43 case UM_QUIT: 44 break; 45 case UM_INPUTR: 46 { 47 cout << "请输入要操作的链表：" << endl; 48 cin >> num; 49 switch (num) 50 { 51 case ListNum0: 52 cout << "请输入数据并以-1结束" << endl; 53 while (cin >> item, item != -1) 54 { 55 Push_Back(mylist, item); 56 } 57 break; 58 case ListNum1: 59 cout << "请输入数据并以-1结束" < > item, item != -1) 61 { 62 Push_Back(mylist1, item); 63 } 64 break; 65 case ListNum2: 66 cout << "请输入数据并以-1结束" << endl; 67 while(cin >> item, item != -1) 68 { 69 Push_Back(mylist2,item); 70 } 71 break; 72 default: 73 cout << "选择错误 请重新选择" << endl; 74 break; 75 } 76 } 77 break; 78 case UM_INPUTH: 79 { 80 cout << "请输入要操作的链表：" << endl; 81 cin >> num; 82 switch (num) 83 { 84 case ListNum0: 85 cout << "请输入数据并以-1结束" << endl; 86 while(cin >>item, item != -1) 87 { 88 Push_Front(mylist, item); 89 } 90 break; 91 case ListNum1: 92 cout << "请输入数据并以-1结束" < >item, item != -1) 94 { 95 Push_Front(mylist1, item); 96 } 97 break; 98 case ListNum2: 99 cout << "请输入数据并以-1结束" << endl;100 while(cin >> item, item != -1)101 {102 Push_Front(mylist2, item);103 }104 break;105 default:106 cout << "选择错误 请重新选择" < > num;115 switch (num)116 {117 case ListNum0:118 Print_List(mylist);119 break;120 case ListNum1:121 Print_List(mylist1);122 break;123 case ListNum2:124 Print_List(mylist2);125 break;126 default:127 cout << "选择错误 请重新选择" << endl;128 break;129 }130 }131 break;132 case UM_ERASE:133 cout << "请输入位置：" << endl;134 cin >> pos;135 Erase(mylist, pos);136 break;137 case UM_REMOVE:138 cout << "请输入要删除的数据：" < > item;140 Remove(mylist, item);141 break;142 case UM_POPFRONT:143 Pop_Front(mylist);144 break;145 case UM_POPBACK:146 Pop_Back(mylist);147 break;148 case UM_INSERT:149 cout << "请输入要插入的数据及位置信息:" << endl;150 cin >> item, pos;151 Insert(mylist, pos, item);152 break;153 case UM_REVERSE:154 Reverse(mylist);155 break;156 case UM_MERGE:157 Merge(mylist, mylist1, mylist2);158 break;159 case UM_LINK:160 Link(mylist, mylist1);161 break;162 default:163 cout << "选择错误! 请重新选择" << endl;164 break;165 }166 }167 DestroyList(mylist);168 } 以上代码分为三部分：头文件，实现文件，测试文件。
当时运行环境为VS2010。
Good Good Study, Day Day Up.
顺序 选择 循环 总结