版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://blog.csdn.net/lady_killer9/article/details/82700743
今天是单链表的实现，主要实现函数如下：
代码：
1 /*
2 Project: single linkeed list (数据结构 单链表)
3 Date: 2018/09/14
4 Author: Frank Yu
5 InitList(LinkList &L) 参数：单链表L 功能：初始化 时间复杂度 O(1)
6 ListLength(LinkList L) 参数：单链表L 功能：获得单链表长度 时间复杂度O(n)
7 ListInsert(LinkList &L,int i,ElemType e) 参数：单链表L,位置i，元素e 功能：位置i后插 时间复杂度O(n)[加入了查找]
8 若已知指针p指向的后插 O(1)
9 ListDelete(LinkList &L,int i) 参数：单链表L，位置i 功能：删除位置i元素 时间复杂度O(n)[加入了查找]
10 若已知p指针指向的删除 最好是O(1),因为可以与后继结点交换数据域，然后删除后继结点。
11 最坏是O(n),即从头查找p之前的结点,然后删除p所指结点
12 LocateElem(LinkList L,ElemType e) 参数：单链表L，元素e 功能：查找第一个等于e的元素，返回指针 时间复杂度O(n)
13 */
14 #include<cstdio>
15 #include<cstdlib>
16 #include<cstring>
17 #include<cmath>
18 #include<iostream>
19 using namespace std;
20 #define Status int
21 #define ElemType int
22 //单链表结点数据结构
23 typedef struct LNode
24 {
25 ElemType data;//数据域
26 struct LNode *next;//指针域
27 }LNode,*LinkList;
28 //**************************基本操作函数***************************//
29 //初始化函数
30 Status InitList(LinkList &L)
31 {
32 L = new LNode;//生成头结点 这样删除等操作就不必分第一个结点和其他了
33 L->next = NULL;
34 return 1;
35 }
36 //获取单链表长度 头结点无数据，不算
37 int ListLength(LinkList L)
38 {
39 LinkList p=L;int sum=0;
40 while(p)
41 {
42 sum++;
43 p=p->next;
44 }
45 return sum-1;//去除头结点
46 }
47 //插入函数--后插法 插入到第i(1<=i<=length+1)个位置 即i-1之后 不必区分i的位置
48 bool ListInsert(LinkList &L,int i,ElemType e)
49 {
50 LNode* s;LinkList p=L;int j=0;
51 while(p&&(j<i-1))//j指到i-1位置
52 {
53 p=p->next;
54 ++j;
55 }
56 if(!p||j>i-1)//i<1或者i>ListLength(L)+1时,插入位置无效 不调用ListLength,提高效率
57 {
58 printf("插入位置无效！！！\n");
59 return false;
60 }
61 s=new LNode;
62 s->data=e;
63 s->next=p->next;
64 p->next=s;
65 return true;
66 }
67 //删除函数 删除位置i的结点 即删除i-1之后的结点
68 bool ListDelete(LinkList &L,int i)
69 {
70 LNode* s;LinkList p=L;int j=0;
71 LinkList q;
72 while(p&&(j<i-1))//j指到i-1位置
73 {
74 p=p->next;
75 ++j;
76 }
77 if(!(p->next)||j>i-1)//i<1或者i>ListLength(L)时,删除位置无效
78 {
79 printf("删除位置无效！！！\n");
80 return false;
81 }
82 q=p->next;
83 p->next=q->next;
84 free(q);//释放空间
85 return true;
86 }
87 //查找函数 按值查找 查找第一个等于e的结点 成功返回该结点指针，否则返回NULL
88 LNode *LocateElem(LinkList L,ElemType e)
89 {
90 LNode *p=L;
91 while(p&&(p->data!=e))
92 {
93 p=p->next;
94 }
95 return p;
96 }
97 //**************************功能实现函数**************************//
98 //遍历输出函数
99 void PrintList(LinkList L)
100 {
101 LinkList p=L->next;//跳过头结点
102 if(ListLength(L))
103 {
104 printf("当前单链表所有元素:");
105 while(p)
106 {
107 printf("%d ",p->data);
108 p=p->next;
109 }
110 printf("\n");
111 }
112 else
113 {
114 printf("当前单链表已空！\n");
115 }
116 }
117 //插入功能函数 调用ListInsert后插
118 void Insert(LinkList &L)
119 {
120 int place;ElemType e;bool flag;
121 printf("请输入要插入的位置(从1开始)及元素:\n");
122 scanf("%d%d",&place,&e);
123 flag=ListInsert(L,place,e);
124 if(flag)
125 {
126 printf("插入成功！！！\n");
127 PrintList(L);
128 }
129 }
130 //删除功能函数 调用ListDelete删除
131 void Delete(LinkList L)
132 {
133 int place;bool flag;
134 printf("请输入要删除的位置(从1开始):\n");
135 scanf("%d",&place);
136 flag=ListDelete(L,place);
137 if(flag)
138 {
139 printf("删除成功！！！\n");
140 PrintList(L);
141 }
142 }
143 //查找功能函数 调用LocateElem查找
144 void Search(LinkList L)
145 {
146 ElemType e;LNode *q;
147 printf("请输入要查找的值:\n");
148 scanf("%d",&e);
149 q=LocateElem(L,e);
150 if(q)
151 {
152 printf("找到该元素！\n");
153 }
154 else
155 printf("未找到该元素！\n");
156 }
157 //菜单
158 void menu()
159 {
160 printf("********1.后插 2.删除*********\n");
161 printf("********3.查找 4.输出*********\n");
162 printf("********5.退出 *********\n");
163 }
164 //主函数
165 int main()
166 {
167 LinkList L;int choice;
168 InitList(L);
169 while(1)
170 {
171 menu();
172 printf("请输入菜单序号：\n");
173 scanf("%d",&choice);
174 if(choice==5) break;
175 switch(choice)
176 {
177 case 1:Insert(L);break;
178 case 2:Delete(L);break;
179 case 3:Search(L);break;
180 case 4:PrintList(L);break;
181 default:printf("输入错误！！！\n");
182 }
183 }
184 return 0;
185 }