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

前言

定义

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;
}

 结果：