数据结构线性链表的创立及其基本操作初始化、遍历、销毁、判空、求表长、删除、插入等

Bertha 。 2022-07-16 12:40 110阅读 0赞

最近写了个数据结构的单链表，其中包括十来个基本操作算法，包括了创建单链表、删除、插入、定位、遍历等基本的操作。在VS上运行了一下，可以通过，感觉还不错，和大家分享一下！

我是建立了一个C++项目，在项目下写的，你们也可以创建项目把下面的东西复制到编译器上试试！

第一部分是头文件1 （一些定义声明等）

\#include<stdio.h>  
\#include<stdlib.h>  
\#define TURE 1  
\#define ERROR 0  
\#define OK 1  
\#define FALSE 0  
\#define OVERFLOW -1  
\#define INIT\_LIST\_SIZE 100  
\#define LISTINCREMENT 10  
typedef int Status;

typedef int ElemType;

typedef struct LNode \{  
ElemType data;  
struct LNode \*next;  
\}LNode,\*LinkList;

第二部分是头文件2（十四个基本操作）

\#include"header.h"  
  
  
  
//1、初始化  
Status INITLIST(LinkList &L)  
\{  
L=(LinkList)malloc(sizeof(LNode));  
if(!L)  
exit(OVERFLOW);  
L->next=NULL;  
return OK;  
\}  
  
  
//2、销毁  
void DestoryList(LinkList &L)  
\{ LinkList p;  
while (L)  
\{  
p=L->next;  
free(L);  
L=p;  
\}  
\}  
  
  
  
  
//3、清空  
void ClearList(LinkList &L)  
\{  
LinkList p=L->next;  
LinkList q;  
while (p)  
\{  
 q=p->next;  
 free(p);  
 p=q;  
\}  
\}  
  
  
//4、判空  
Status EmptyList(LinkList L)  
\{  
if(!L->next)  
return TURE;  
else  
return FALSE;  
\}  
//5、求表长  
Status LengthList(LinkList L)  
\{  
int n=0;  
LinkList p;  
p=L->next;  
while (p)  
\{  
n++;  
p=p->next;  
\}  
return n;  
\}  
  
  
  
  
//6、取值  
Status GetElem(LinkList &L,int i)  
\{  
int j=1,e;  
LinkList p;  
p=L->next;  
for (; p&&j < i; j++)  
\{  
p=p->next;  
\}  
if(!p||j>i)  
return ERROR;  
e=p->data;  
return e;  
\}  
  
  
  
  
//7、定位  
Status LocateList(LinkList L,ElemType e)  
\{  
int i=0;  
LinkList p;  
p=L->next;  
while (p)  
\{  
if(e==p->data)  
return i+1;  
else  
\{  
i++;  
p=p->next;  
\}  
\}  
  
  
  
\}  
  
  
//8、求前驱  
Status ElemPrimer(LinkList L, ElemType e)  
\{  
LinkList p=L->next,q=p->next;  
while (q)  
\{  
if (e == q->data)  
return p->data;  
else  
p=q;  
q=p->next;  
\}  
\}  
  
  
//9、求后继  
Status ElemNext(LinkList L, ElemType e)  
\{  
int i=0;  
LinkList p=L->next,q=NULL;  
while (p)  
\{  
if (e == p->data)  
\{  
q=p->next;  
return q->data;  
\}  
else  
p=p->next;  
i++;  
\}  
\}  
  
  
//10、遍历  
void TraverLinkList(LinkList L)  
\{ LinkList p=L->next;  
while (p)  
\{  
printf("%5d",p->data);  
p=p->next;  
\}  
\}  
  
  
//11、插入  
void InsertELem(LinkList &L,int i,ElemType e)  
\{  
int j=0;  
LinkList p;  
LinkList s;  
p=L;  
s=(LinkList)malloc(sizeof(LNode));  
for (; p&&j<i-1; j++)  
\{  
p=p->next;  
\}  
if(!p||j>i)  
s->next=p->next;  
p->next=s;  
s->data=e;  
\}  
//12、删除  
void DeleteElem(LinkList &L,int i)  
\{  
int j=0,e;  
LinkList p,q;  
p=L;  
for (; p&&j < i - 1; j++)  
p=p->next;  
q=p->next;  
p->next=q->next;  
free(q);  
\}  
  
  
//13、逆序建立单链表  
LinkList CreateList\_B(LinkList &L, int n)  
\{ int i;  
LinkList p;  
L=(LinkList)malloc(sizeof(LNode));  
L->next=NULL;  
for (i = 0; i < n; i++)  
\{  
p=(LinkList)malloc(sizeof(LNode));  
p->next=L->next;  
L->next=p;  
\}  
return L;  
\}  
  
  
  
//14、顺序建立单链表  
LinkList CreateLinkList(int n)  
\{  
int length,i,value; //有效结点的长度 //用来存放用户输入的结点的值  
//创建了一个不存放有效数据的头结点  
LinkList L= (LinkList)malloc(sizeof(LNode));  
if (NULL == L)  
\{  
printf("内存分配失败，程序退出！\\n");  
exit(-1);  
\}  
LinkList q = L; //q始终指向尾结点  
q->next = NULL; //清空指针域  
printf("\\n");  
for (i = 0; i<n; i++)  
\{  
printf("请输入第%d个结点的值：", i + 1);  
scanf\_s("%d", &value);printf("\\n");  
LinkList p = (LinkList)malloc(sizeof(LNode));  
p->data = value; //向新结点中放入值  
q->next = p; //将尾结点指向新结点  
p->next = NULL; //将新结点的指针域清空  
q = p; //将新结点赋给pTail,使pTail始终指向为尾结点  
\}  
return L;  
\}

最后一本分是主函数也是测试函数，我在VS上运行后可以编译运行

\#include "stdafx.h"  
\#include"header1.h"  
  
  
int main()  
\{  
int n,i,e,w,x,y;  
LinkList L;  
INITLIST(L);//初始化测试  
printf("准备创建链表......\\n\\n");  
printf("请输入您想要创建链表结点的个数: ");  
scanf\_s("%d", &n);  
L=CreateLinkList(n); //创建链表测试  
printf("您创建了包含%d个结点的链表\\n",LengthList(L));//求表长  
printf("\\n您输入的元素为：");  
TraverLinkList(L);//遍历测试  
printf("\\n");  
x:printf("\\n请输入你想取出的结点：");//取元素测试  
scanf\_s("%d",&i);  
if (i<1 || i>n)  
\{  
printf("\\n错误！！请重新输入！");  
printf("\\n");  
goto x;  
\}  
printf("\\n该结点的值为：%d",GetElem(L,i));//定位  
printf("\\n");  
printf("请输入你想定位的元素: ");  
scanf\_s("%d",&e);  
printf("\\n该元素的位置是：%d",LocateList(L,e));  
w:printf("\\n请输入你想求那个元素的后继：");//后继测试  
scanf\_s("%d",&e);  
if (e>=n)  
\{  
printf("\\n错误！！请重新输入！");  
printf("\\n");  
goto w;  
\}  
printf("\\n该元素的后继是：%d",ElemNext(L,e));  
y:printf("\\n请输入你想求那个元素的前驱：");//前驱测试  
scanf\_s("%d", &e);  
if (e<1)  
\{  
printf("\\n错误！！请重新输入！");  
printf("\\n");  
goto y;  
\}  
printf("\\n该元素的前驱是：%d", ElemPrimer(L, e));  
printf("\\n请输入你要删除的结点的位置：");//删除测试  
scanf\_s("%d",&i);  
DeleteElem(L, i);  
printf("\\n现在的元素为：");  
TraverLinkList(L);  
printf("\\n请输入你要插入的节点的位置：");//插入测试  
scanf\_s("%d",&i);  
printf("\\n输入你要插入的元素：");  
scanf\_s("%d",&e);  
InsertELem(L,i,e);  
TraverLinkList(L);  
printf("\\n测试成功！\\n");  
return 0;  
\}

最后有什么问题可以私信！