C/C++数据结构-链表的测试题

前言

链表是表示一系列结点的数据结构。链表由结点组成,每个结点包含结点值以及指向其他结点的指针。

链表的种类包括单向链表、双向链表和循环链表。单向链表中的每个结点包含一个指针,指向链表中的后一个结点。双向链表中的每个结点包含两个指针,分别指向链表中的前一个结点和后一个结点。

结点

链表中一个数据元素需要存储本身的信息,还需要存储直接后继的存储位置,这两部分构成结点(node)

换种方式来说,一个结点需要包含两部分内容,数据域和指针域

数据域:存储数据元素信息

指针域:存储直接后继的存储位置

如下所示为一个结点,data表示数据域,next表示指针域。

实验内容

定义

1)类型定义linklistDef.h

typedef struct LNode

{

ElemType data;

struct LNode *next;

}LNode , *LinkList;

 

(2)线性链表的基本操作linklistAlgo.h

Status ListInit_Link(LinkList &L)

{ /* 操作结果:构造一个空的线性表 L */

//L=(LinkList)malloc(sizeof(struct LNode));

L=new LNode;

if(!L)

exit(OVERFLOW);

L->next=NULL;

return OK;

}

获取长度

int ListLength_Link (LinkList L)

{ /* 初始条件:线性表 L已存在。*/

/* 操作结果:返回 L中数据元素个数 */

int i=  0   ;

LinkList p=L->next;

while(p)

{ i=i+1;

p=p->next;

}

return i;

}

获取元素

Status GetElem_Link (LinkList L,int i,ElemType &e)

{ /* 初始条件: L为带头结点的单链表的头指针*/

/* 操作结果:当第 i个元素存在时,其值赋给 e并返回 OK,否则返回ERROR */

int j=1;

LinkList p=L->next;

while(p&&j<i)

{ p=p->next;

j++;

}

if(!p||j>i)

return ERROR;

e=p->data;

return OK;

}

插入

Status ListInsert_Link (LinkList L,int i,ElemType e)

{ /* 在带头结点的单链线性表 L中第 i个位置之前插入元素 e */

int j=0;

LinkList p=L,s;

while(p&&j<i-1)

{ p=p->next;

j++;

}

if(!p||j>i-1)

return ERROR;

s=new LNode;

s->data=e;

s->next=p->next;

p->next=s;

return OK;

}

删除

Status ListDelete_Link (LinkList L,int i,ElemType &e)

{ /* 在带头结点的单链线性表 L中,删除第 i个元素,并由 e返回其值 */

int j=0;

LinkList p=L,q;

while(p->next&&j<i-1)

{p=p->next;

j++;

}

if(!p->next||j>i-1)

return ERROR;

q=p->next;

p->next=q->next;

e=q->data;

delete q;

return OK;

}

遍历输出

Status ListTraverse_Link (LinkList L)

{ /* 初始条件:线性表L已存在 */

/* 操作结果:依次对 L的每个数据元素的值进行输出 */

LinkList p=L->next;

while(p)

{printf("%d  ",p->data);

p=p->next;

}

printf("\n");

return OK;

}

创建链表

void CreateList2_Link (LinkList &L,int n)

{ /* 正位序(插在表尾)输入 n 个元素的值,建立带表头结构的单链线性表 */

int i;

LinkList p,q;

L=new LNode;

L->next=NULL;

q=L;

printf("请输入%d个数据\n",n);

for(i=1;i<=n;i++)

{

p=new LNode;

scanf("%d",&p->data);

      q->next        =p;

q=        p        ;

}

       p->next        =NULL;

}

分析:p用作临时指针存放输入的数据,每次循环需要保存上一个指针,所以推出      q->next        =p; q=        p        ;

最终p或q->next需要变成NULL,保证最后一个元素的Next域不存在数据。

测试

#include"pubuse.h"
typedef int ElemType;
#include"linklistDef.h"
#include"linklistAlgo.h"
int main()
{ int n=5;
LinkList La;
int i;
ElemType e;
printf("链表内容, ");
CreateList2_Link (La,n); 
printf("La="); 
ListTraverse_Link (La);
printf("\n 输入要取第几个元素 : ");
scanf("%d",&i);
if(GetElem_Link (La,i,e)) 
   printf("\n所对应的元素 e=%d\n",e);
else
   printf("input error!\n"); 
printf("\n 输入插入位置和插入的元素 : ");
scanf("%d %d",&i,&e);
if(ListInsert_Link (La,i,e))
{
printf("La="); 
ListTraverse_Link (La);}
else
   printf("input error!\n"); 
printf("\n 输入所要删除的元素位序 : ");
scanf("%d",&i);
if(ListDelete_Link (La,i,e)) 
{  printf("\n所删除的元素 e=%d\n",e);  
   printf("La="); 
   ListTraverse_Link (La);
}
else
   printf("input error!\n"); 
return 0;
}

 结果:

作者:Miracle
来源:麦瑞克博客
链接:https://www.unitymake.com/archives/programming-life/datastruct/1993
本博客所有文章除特别声明外,均采用CC BY-NC-SA 4.0许可协议,转载请注明!
THE END
分享
打赏
海报
C/C++数据结构-链表的测试题
前言 链表是表示一系列结点的数据结构。链表由结点组成,每个结点包含结点值以及指向其他结点的指针。 链表的种类包括单向链表、双向链表和循环链表。单向链……
<<上一篇
下一篇>>
文章目录
关闭
目 录