数据结构--线性表及其应用

实验一 线性表及其应用

一、实验目的

1.熟悉C语言的上机环境，进一步掌握C语言的结构特点。 2.掌握线性表的顺序存储结构的定义及C语言实现。

3.掌握线性表的链式存储结构——单链表的定义及C语言实现。 4.掌握线性表在顺序存储结构即顺序表中的各种基本操作。 5.掌握线性表在链式存储结构——单链表中的各种基本操作。 二、实验内容

1.顺序线性表的建立、插入及删除。 2.链式线性表的建立、插入及删除。 三、实验步骤

1.建立含n个数据元素的顺序表并输出该表中各元素的值及顺序表的长度。 2.利用前面的实验先建立一个顺序表L={21，23，14，5，56，17，31}，然后在第i个位置插入元素68。

3.建立一个带头结点的单链表，结点的值域为整型数据。要求将用户输入的数据按尾插入法来建立相应单链表。 四、实现提示

1.由于C语言的数组类型也有随机存取的特点，一维数组的机内表示就是顺序结构。因此，可用C语言的一维数组实现线性表的顺序存储。

在此，我们利用C语言的结构体类型定义顺序表： #define MAXSIZE 1024

typedef int elemtype; /* 线性表中存放整型元素 */ typedef struct

{ elemtype vec[MAXSIZE];

int len; /* 顺序表的长度 */ }sequenlist;

将此结构定义放在一个头文件sqlist.h里，可避免在后面的参考程序中代码重复书写，另外在该头文件里给出顺序表的建立及常量的定义。

2. 注意如何取到第i个元素，在插入过程中注意溢出情况以及数组的下标与

1

位序（顺序表中元素的次序）的区别。

3.单链表的结点结构除数据域外，还含有一个指针域。用C语言描述结点结构如下：

typedef int elemtype;

typedef struct node { elemtype data; //数据域 struct node *next; //指针域 }linklist;

注意结点的建立方法及构造新结点时指针的变化。构造一个结点需用到C语言的标准函数malloc()，如给指针变量p分配一个结点的地址：

p=(linklist *)malloc(sizeof(linklist));该语句的功能是申请分配一个类型为linklist的结点的地址空间，并将首地址存入指针变量p 中。当结点不需要时可以用标准函数free(p)释放结点存储空间，这时p为空值（NULL）。 五、思考与提高

1. 如果按由表尾至表头的次序输入数据元素，应如何建立顺序表。 2. 在main函数里如果去掉L=&a语句，会出现什么结果？ 六、完整参考程序

1.顺序线性表的建立、插入及删除。

#include #include

#define MAX 30 //定义线性表的最大长度 enum BOOL{False,True}; //定义BOOL型 typedef struct{

char elem[MAX]; //线性表

int last; //last指示当前线性表的长度 }sqlist;

void initial(sqlist &); //初始化线性表

BOOL insert(sqlist &,int,char); //在线性表中插入元素 BOOL del(sqlist&,int,char &); //在线性表中删除元素 int locate(sqlist,char); //在线性表中定位元素 void print(sqlist); //显示线性表中所有元素 void main()

{sqlist S; //S为一线性表 int loc,flag=1; char j,ch;

2

BOOL temp;

printf(\本程序用来实现顺序结构的线性表。\\n\ printf(\可以实现查找、插入、删除等操作。\\n\ initial(S); //初始化线性表 while(flag)

{ printf(\请选择:\\n\ printf(\显示所有元素\\n\ printf(\插入一个元素\\n\ printf(\删除一个元素\\n\ printf(\查找一个元素\\n\ printf(\退出程序 \\n\ scanf(\ switch(j)

{case '1':print(S); break; //显示所有元素

case '2':{printf(\请输入要插入的元素(一个字符)和插入位置:\\n\ }

printf(\格式：字符，位置；例如:a,2\\n\

scanf(\ //输入要插入的元素和插入的位置 temp=insert(S,loc,ch); //插入

if(temp==False) printf(\插入失败!\\n\ //插入失败 break; }

scanf(\ //输入要删除的元素的位置 temp=del(S,loc,ch); //删除

if(temp==True) printf(\删除了一个元素:%c\\n\删除成功 else printf(\该元素不存在!\\n\ //删除失败 print(S); break; }

scanf(\ //输入要查找的元素 loc=locate(S,ch); //定位

if(loc!=-1) printf(\该元素所在位置:%d\\n\显示该元素位置 else printf(\不存在!\\n\当前元素不存在 break; }

else {printf(\插入成功!\\n\ print(S);} //插入成功

case '3':{printf(\请输入要删除元素的位置:\

case '4':{printf(\请输入要查找的元素:\

default:flag=0;printf(\程序结束，按任意键退出!\\n\

} getch(); }

void initial(sqlist &v)

3

{//初始化线性表 int i;

printf(\请输入初始线性表长度：n=\输入线性表初始化时的长度 scanf(\

printf(\请输入从1到%d的各元素(字符)，例如:abcdefg\\n\ getchar();

for(i=0;i

BOOL insert(sqlist &v,int loc,char ch) {//插入一个元素，成功返回True，失败返回False int i;

if((loc<1)||(loc>v.last+1))

{printf(\插入位置不合理!\\n\ //位置不合理 return False; }

else if(v.last>=MAX) //线性表已满 {printf(\线性表已满!\\n\ return False; }

else {for(i=v.last-1;i>=loc-1;i--) v.elem[i+1]=v.elem[i];//其后元素依次后移 v.elem[loc-1]=ch; //插入元素

v.last++; //线性表长度加一 return True; } }

BOOL del(sqlist &v,int loc,char &ch)

{//删除一个元素，成功返回True，并用ch返回该元素值，失败返回False int j;

if(loc<1||loc>v.last) //删除位置不合理 return False;

else {ch=v.elem[loc-1]; //ch取得该元素值

for(j=loc-1;j

int locate(sqlist v,char ch)

{//在线性表中查找ch的位置，成功返回其位置，失败返回-1 int i=0;

while(i

4

if(v.elem[i]==ch) //找到当前元素 return i; else return(-1); }

void print(sqlist v) //显示当前线性表所有元素 {int i;

for(i=0;i

2.链式线性表的建立、插入及删除。 #include #include #include

#define LEN sizeof(LNode) //定义LEN为一个节点的长度 enum BOOL{False,True}; //定义BOOL型 typedef struct node {char data; //数据域

struct node *next;//指向下一个节点的指针 }LNode,*LinkList;

void CreatList(LinkList &,int); //生成一个单链表

BOOL ListInsert(LinkList &,int,char); //在单链表中插入一个元素 BOOL ListDelete(LinkList &,int,char &); //在单链表中删除一个元素 BOOL ListFind_keyword(LinkList,char,int &); //按关键字查找一个元素 BOOL ListFind_order(LinkList,char &,int); //按序号查找一个元素 void ListPrint(LinkList); //显示单链表所有元素 void main() {LinkList L; BOOL temp; int num,loc,flag=1; char j,ch;

printf(\本程序实现链式结构的线性表的操作。\\n\ printf(\可以进行插入，删除，定位，查找等操作。\\n\

printf(\请输入初始时链表长度:\输入生成单链表时的元素个数 scanf(\

CreatList(L,num); //生成单链表 ListPrint(L); while(flag)

{ printf(\请选择:\\n\

printf(\显示所有元素\\n\ //显示链表元素 printf(\插入一个元素\\n\ //插入链表元素 printf(\删除一个元素\\n\ //删除链表元素 printf(\按关键字查找元素\\n\ //按关键字查找 printf(\按序号查找元素\\n\按序号查找

5

本文来源：https://www.bwwdw.com/article/jwut.html