《数据结构实验指导书(2010级)》由会员分享，可在线阅读，更多相关《数据结构实验指导书(2010级)（101页珍藏版）》请在金锄头文库上搜索。
1、数 据 结 构 实 验 指 导 书计算机学院专业基础教研室2008 年 3 月实验一 线性表及其应用一、一、实验实验目的目的1.熟悉 C 语言的上机环境，进一步掌握 C 语言的结构特点。2.掌握线性表的顺序存储结构的定义及 C 语言实现。3.掌握线性表的链式存储结构单链表的定义及 C 语言实现。4.掌握线性表在顺序存储结构即顺序表中的各种基本操作。5.掌握线性表在链式存储结构单链表中的各种基本操作。二、二、实验实验内容内容1.顺序线性表的建立、插入及删除。2.链式线性表的建立、插入及删除。三、三、实验实验步步骤骤1.建立含 n 个数据元素的顺序表并输出该表中各元素的值及顺序表的长度。2.利用前
2、面的实验先建立一个顺序表 L=21，23，14，5，56，17，31，然后在第 i 个位置插入元素 68。3.建立一个带头结点的单链表，结点的值域为整型数据。要求将用户输入的数据按尾插入法来建立相应单链表。四、四、实现实现提示提示1.由于 C 语言的数组类型也有随机存取的特点，一维数组的机内表示就是顺序结构。因此，可用 C 语言的一维数组实现线性表的顺序存储。在此，我们利用 C 语言的结构体类型定义顺序表：#define MAXSIZE 1024typedef int elemtype; /* 线性表中存放整型元素 */typedef struct elemtype vecMAXSIZE;in
3、t len; /* 顺序表的长度 */sequenlist;将此结构定义放在一个头文件 sqlist.h 里，可避免在后面的参考程序中代码重复书写，另外在该头文件里给出顺序表的建立及常量的定义。2. 注意如何取到第 i 个元素，在插入过程中注意溢出情况以及数组的下标与位序（顺序表中元素的次序）的区别。3.单链表的结点结构除数据域外，还含有一个指针域。用 C 语言描述结点结构如下：typedef int elemtype;typedef struct node elemtype data; /数据域struct node *next; /指针域linklist;注意结点的建立方法及构造新结点时指
4、针的变化。构造一个结点需用到C 语言的标准函数 malloc()，如给指针变量 p 分配一个结点的地址：p=(linklist *)malloc(sizeof(linklist);该语句的功能是申请分配一个类型为linklist 的结点的地址空间，并将首地址存入指针变量 p 中。当结点不需要时可以用标准函数 free(p)释放结点存储空间，这时 p 为空值（NULL）。五、思考与提高五、思考与提高1. 如果按由表尾至表头的次序输入数据元素，应如何建立顺序表。2. 在 main 函数里如果去掉 L= /定义 BOOL 型typedef structchar elemMAX; /线性表int la
5、st; /last 指示当前线性表的长度sqlist;void initial(sqlist /初始化线性表BOOL insert(sqlist /在线性表中插入元素BOOL del(sqlist /在线性表中删除元素int locate(sqlist,char); /在线性表中定位元素void print(sqlist); /显示线性表中所有元素void main()sqlist S; /S 为一线性表int loc,flag=1;char j,ch;BOOL temp;printf(“本程序用来实现顺序结构的线性表。n“);printf(“可以实现查找、插入、删除等操作。n“);initi
6、al(S); /初始化线性表while(flag) printf(“请选择:n“);printf(“1.显示所有元素n“);printf(“2.插入一个元素n“);printf(“3.删除一个元素n“);printf(“4.查找一个元素n“);printf(“5.退出程序 n“);scanf(“ %c“,switch(j)case 1:print(S); break; /显示所有元素case 2:printf(“请输入要插入的元素(一个字符)和插入位置:n“);printf(“格式：字符，位置；例如:a,2n“);scanf(“ %c,%d“, /输入要插入的元素和插入的位置temp=inse
7、rt(S,loc,ch); /插入if(temp=False) printf(“插入失败!n“); /插入失败else printf(“插入成功!n“); print(S); /插入成功break;case 3:printf(“请输入要删除元素的位置:“);scanf(“%d“, /输入要删除的元素的位置temp=del(S,loc,ch); /删除if(temp=True) printf(“删除了一个元素:%cn“,ch); /删除成功else printf(“该元素不存在!n“); /删除失败print(S);break;case 4:printf(“请输入要查找的元素:“);scanf(
8、“ %c“, /输入要查找的元素loc=locate(S,ch); /定位if(loc!=-1) printf(“该元素所在位置:%dn“,loc+1); /显示该元素位置else printf(“%c 不存在!n“,ch);/当前元素不存在break;default:flag=0;printf(“程序结束，按任意键退出!n“);getch();void initial(sqlist printf(“请输入初始线性表长度：n=“); /输入线性表初始化时的长度scanf(“%d“,printf(“请输入从 1 到%d 的各元素(字符)，例如:abcdefgn“,v.last);getchar(
9、);for(i=0;iv.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.elemi+1=v.elemi;/其后元素依次后移v.elemloc-1=ch; /插入元素v.last+; /线性表长度加一return True;BOOL del(sqlist if(locv.last) /删除位置不合理return False;else ch=v.elemloc-1; /c
10、h 取得该元素值for(j=loc-1;j#include #include #define LEN sizeof(LNode) /定义 LEN 为一个节点的长度enum BOOLFalse,True; /定义 BOOL 型typedef struct nodechar data; /数据域struct node *next;/指向下一个节点的指针LNode,*LinkList;void CreatList(LinkList /生成一个单链表BOOL ListInsert(LinkList /在单链表中插入一个元素BOOL ListDelete(LinkList /在单链表中删除一个元素BOO
11、L ListFind_keyword(LinkList,char,int /按关键字查找一个元素BOOL ListFind_order(LinkList,char /按序号查找一个元素void ListPrint(LinkList); /显示单链表所有元素void main()LinkList L;BOOL temp;int num,loc,flag=1;char j,ch;printf(“本程序实现链式结构的线性表的操作。n“);printf(“可以进行插入，删除，定位，查找等操作。n“);printf(“请输入初始时链表长度:“); /输入生成单链表时的元素个数scanf(“%d“,Cre
12、atList(L,num); /生成单链表ListPrint(L); while(flag) printf(“请选择:n“);printf(“1.显示所有元素n“); /显示链表元素printf(“2.插入一个元素n“); /插入链表元素printf(“3.删除一个元素n“); /删除链表元素printf(“4.按关键字查找元素n“); /按关键字查找printf(“5.按序号查找元素n“); /按序号查找printf(“6.退出程序 n“); /退出scanf(“ %c“,switch(j)case 1:ListPrint(L); break;case 2:printf(“请输入元素(一个字
13、符)和要插入的位置:n“);printf(“格式:字符，位置；例如:a,3n“);scanf(“ %c,%d“, /输入要插入的元素和要插入的位置temp=ListInsert(L,loc,ch); /插入if(temp=False) printf(“插入失败!n“); /插入失败else printf(“插入成功!n“); /成功插入ListPrint(L);break;case 3:printf(“请输入要删除的元素所在位置:“);scanf(“%d“, /输入要删除的节点的位置temp=ListDelete(L,loc,ch); /删除if(temp=False) printf(“删除失
14、败!n“); /删除失败else printf(“成功删除了一个元素:%cn“,ch); /删除成功，显示该元素ListPrint(L);break;case 4:if(L-next=NULL) /链表为空printf(“链表为空!n“);elseprintf(“请输入要查找的元素(一个字符):“);scanf(“ %c“, /输入要查找的元素temp=ListFind_keyword(L,ch,loc); /按关键字查找if(temp=False) printf(“没有找到该元素!n“); /查找失败else printf(“该元素在链表的第%d 个位置。n“,loc); /成功查找，显示该
15、元素位置break;case 5:if(L-next=NULL) /链表为空printf(“链表为空!n“);elseprintf(“请输入要查找的位置:“);scanf(“%d“, /输入要查找的元素的位置temp=ListFind_order(L,ch,loc); /按序号查找if(temp=False) printf(“该位置不存在!n“); /查找失败else printf(“第%d 个元素是：%cn“,loc,ch);/成功查找，显示该元素break;default:flag=0;printf(“程序结束，按任意键退出!n“);getch();void CreatList(LinkList LinkList p;v=
