基于c语言，严蔚敏版数据结构的线性表节本操作

[注解]：下面贴出的代码实严蔚敏版的数据结构的线性表的数据结构+操作，第一，这既是完整的程序，也是数据结构的起始部分，全书所涉及到的链表的操作都可基于此基础代码，包括后面的排序，合并etc；第二，为了 以后用户操作方便，我将链表的数据结构及其操作封装在了头文件里，当用户想调用写好的基本操作时，只需要导入头文件和源代码，最后在自己的代码中包含头文件即可（可以把它想象成类库）；第三：代码的简略性：代码比较简单，可能对数据的容错能力稍低，只测试了正确的数据，所以用户想完善代码可以自行完善。如有错误也欢迎指教；第四：建议：如果觉得有阅读困难的建议去读一下c语言的结构体和指针部分（c++也可），相信弄懂那部分后自然就会迎刃而解啦。

头文件“ADT.H”:

#include<malloc.h>
#include<stdio.h>
#include<stdlib.h>
/*#define TRUE 1//状态码与FLAG已经注释掉了，如需要规范可以开启
#define FALSE 0
#define OK 0
#define ERROR 0
#define OVERFLOW 0
#typedef int Status
#typedef int ElemType*/ 
typedef struct ListNode {
int data;
ListNode *next;
int length;
}*List;//定义节点的结构体以及一个指向节点的List指针


bool InitList(List &L);//初始化线性表
bool ClearList(List &L);//将线性表置空
bool DestroyList(List &L);//销毁线性表
bool ListEmpty(List L);//判断线性表是否为空
int ListLength(List L);//判断线性表的长度
bool GetElem(List L,int i,int &e);//查找线性表中位序为i的数值，并返还给e
int LocateItem(List L,int e);//寻找List中数值为e的位序i
void PriorElem(List L,int cur_e,int &e);//修改线性表中数值为cur_e的前驱节点数值为pre_e
void NextElem(List L,int pre_e,int &e);//修改线性表中数值为cur_e的后继节点数值为next_e
void ListInsert(List &L,int i,int e);//在位序为i的前一个位置插入数值为e的节点
int ListDelete(List &L,int i,int &e);//删除位序为i位置的数据并且将删除的数据返还给数值e
void ListTravers(List L);//按位序输出线性表中的数据

List.cpp:

#include<stdlib.h>
#include <stdio.h>
#include<malloc.h>
typedef struct ListNode {
int data;
ListNode *next;
int length;
}*List;


bool InitList(List &L);
bool ClearList(List &L);
bool DestroyList(List &L);
bool ListEmpty(List L);
int ListLength(List L);
bool GetElem(List L, int i, int &e);
int LocateItem(List L,int e);
void PriorElem(List L,int cur_e,int &pre_e);
void NextElem(List L,int cur_e,int &next_e);
void  ListInsert(List &L, int i, int e);
void InsertList(List &L, int e);
int ListDelete(List &L,int i,int &e);
void ListTravers(List L);


bool InitList(List &L) {
//ListNode* L=(ListNode*)malloc(sizeof(ListNode));//如果不是初始化形参的ListNode，也可以用这种形式
L = (List)malloc(sizeof(ListNode));//这个地方不能用*ListNode否则会显示重复定义~~
if (!L)
return false;
L->next = NULL;
L->length=0;
printf("初始化链表成功！\n");
return true;
}
bool DestroyList(List &L) {//原理：从链表的头指针指向的节点逐步向下释放
ListNode *p = (ListNode *)malloc(sizeof(ListNode));
ListNode *q = (ListNode *)malloc(sizeof(ListNode));
p = L->next;
while (p) {
q = p->next;//从头指针开始逐步向下释放
free(p);
p = q;
}
L->next = NULL;//最后设置头指针为空
printf("链表已经被销毁！\n");
return true;
}
bool ClearList(List &L) {
L->length = 0;//指针调用成员用这个，若果是结构体用.
L->next=NULL;
return true;
}
int ListLength(List L) {
return L->length;
}
bool ListEmpty(List L) {
if (L->next)
return true;
return false;
}
bool GetElem(List L, int i, int &e) {
ListNode *p = (ListNode *)malloc(sizeof(ListNode));
p = L;
for (int j = 0; j<i; j++) {
if (p)
p = p->next;
}
e=p->data;
printf("替换成功！\n");
return true;
}
int LocateItem(List L, int e) {
ListNode * p = (ListNode *)malloc(sizeof(ListNode));
int h = 1;
p = L;
if (p->next->data!=e){
h++;
}
if(h==L->length+1){
printf("没有查找到该数值！\n");
}
else {
printf("数值为%d的位置为：%d\n", e, h);
         return h;
}


}
void PriorElem(List L, int cur_e, int & pre_e) {
int h = LocateItem(L,cur_e);
if (h > 1)
{
ListNode *p = (ListNode *)malloc(sizeof(ListNode));
p = L;
for (int i = 0; i < h - 1; i++)
p = p->next;
p->data = pre_e;
printf("前驱节点赋值成功！\n");
}
    if (h == 0)
printf("所查找的值不存在");
if(h==1)
printf("所查找的当前值没有前驱节点\n");
}
void NextElem(List L, int cur_e, int &next_e) {
int h = LocateItem(L, cur_e);
if (h>0&&h<L->length)
{
ListNode *p = (ListNode *)malloc(sizeof(ListNode));
p = L;
for (int i = 0; i < h+1; i++)
p = p->next;
p->data = next_e;
printf("后继节点赋值成功！\n");
}
if (h == 0)
printf("所查找的值不存在\n");
if (h == L->length)
printf("所查找的当前值没有后继节点\n");
}
void InsertList(List &L, int e) {
ListNode *p = (ListNode *)malloc(sizeof(ListNode));
p = L;
while (p->next) {
p = p->next;
}
ListNode *q = (ListNode *)malloc(sizeof(ListNode));
q->next = p->next;
p->next = q;
q->data = e;
}
void ListInsert(List &L, int i, int e) {
ListNode *p = (ListNode *)malloc(sizeof(ListNode));
ListNode *q = (ListNode *)malloc(sizeof(ListNode));
p = L;
L->length = L->length + 1;
for (int j = 0; j<i-1; j++)
if(p->next)
      p = p->next;
q->next = p->next;
p->next = q;
q->data = e;
printf("数据插入成功！\n");
}
int ListDelete(List &L, int i, int &e) {
ListNode * p = (ListNode *)malloc(sizeof(ListNode));
ListNode * q = (ListNode *)malloc(sizeof(ListNode));
p = L;
if (p) {
for (int j = 0; j < i-1;j++) {
p = p->next;
}
q = p->next;
p->next = q->next;
e = q->data;
printf("节点数据删除成功！\n");
return e;
}
}
void ListTravers(List L) {
ListNode *p = (ListNode *)malloc(sizeof(ListNode));
p = L->next;
while (p) {
printf("%d\n", p->data);
p = p->next;
}
}
void main() {
List L;
int i;
int e;
int location;
printf("1:初始化线性表\n2:销毁线性表\n3：将线性表置空\n4:判断线性表的长度\n"
"5:替换指定位置的数据\n6:查找元素值为e的位置\n7：修改前驱节点的值为e\n"
"8:修改后继节点的值为e\n9:在位置为i的元素前面插入e\n10:删除位序为i的元素\n11:按照位序输出线性表元素的位置\n");
while (1) {
printf("请选择操作序号：\n");
scanf("%d",&i);//输入的格式化字符串不可省略
switch (i)
{
case 1:
InitList(L);
break;
case 2:
DestroyList(L);
break;
case 3:
ClearList(L);
break;
case 4:
printf("线性表的长度为：%d", ListLength(L));
break;
case 5:
printf("请输入要替换的位置和数值：\n");
scanf("%d%d", &i,&e);
GetElem(L, i, e);
break;
case 6:
printf("请输入要查找的数值：\n");
scanf("%d", &e);
LocateItem(L, e);
break;
case 7:
printf("请输入要查找的数值和前驱节点替换值：");
scanf("%d%d", &i, &e);
PriorElem(L, i, e);
break;
case 8:
printf("请输入要查找的数值和后继节点的替换值：");
scanf("%d%d", &i, &e);
NextElem(L, i, e);
break;
case 9:
printf("请输入前驱节点插入的位置和数值");
scanf("%d%d", &i, &e);
ListInsert(L, i, e);
break;
case 10:
printf("请输入要删除的数据的位置");
scanf("%d", &i, &e);
ListDelete(L, i, e);
break;
case 11:
ListTravers(L);
break;
default:
break;
}
}
}