数据结构实验指导书

1、数据结构实验指导书实验一 线性表及其应用一、实验目的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.建立一个带

2、头结点的单链表，结点的值域为整型数据。要求将用户输入的数据按尾插入法来建立相应单链表。四、实现提示1.由于C语言的数组类型也有随机存取的特点，一维数组的机内表示就是顺序结构。因此，可用C语言的一维数组实现线性表的顺序存储。在此，我们利用C语言的结构体类型定义顺序表：#define MAXSIZE  1024typedef  int  elemtype;    /*  线性表中存放整型元素  */typedef struct elemtype vecMAXSIZE;  int len;  

3、;           /*  顺序表的长度  */ sequenlist;将此结构定义放在一个头文件sqlist.h里，可避免在后面的参考程序中代码重复书写，另外在该头文件里给出顺序表的建立及常量的定义。2. 注意如何取到第i个元素，在插入过程中注意溢出情况以及数组的下标与位序（顺序表中元素的次序）的区别。3.单链表的结点结构除数据域外，还含有一个指针域。用C语言描述结点结构如下：    typedef int elemtype;ty

4、pedef struct node    elemtype data;   /数据域      struct node *next; /指针域     linklist;    注意结点的建立方法及构造新结点时指针的变化。构造一个结点需用到C语言的标准函数malloc()，如给指针变量p分配一个结点的地址：p=(linklist *)malloc(sizeof(linklist);该语句的功能是申请分配一个类型为linklis

5、t的结点的地址空间，并将首地址存入指针变量p 中。当结点不需要时可以用标准函数free(p)释放结点存储空间，这时p为空值（NULL）。五、思考与提高1. 如果按由表尾至表头的次序输入数据元素，应如何建立顺序表。2. 在main函数里如果去掉L=&a语句，会出现什么结果？六、完整参考程序 1.顺序线性表的建立、插入及删除。#include <stdio.h>#include <conio.h>#define MAX 30 /定义线性表的最大长度enum BOOLFalse,True; /定义BOOL型typedef struct char elemMAX; /线

6、性表 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; BOOL temp;prin

7、tf("本程序用来实现顺序结构的线性表。n"); printf("可以实现查找、插入、删除等操作。n"); initial(S); /初始化线性表 while(flag) printf("请选择:n"); printf("1.显示所有元素n"); printf("2.插入一个元素n"); printf("3.删除一个元素n"); printf("4.查找一个元素n"); printf("5.退出程序 n"); scanf("

8、%c",&j); switch(j)case '1':print(S); break; /显示所有元素 case '2':printf("请输入要插入的元素(一个字符)和插入位置:n"); printf("格式：字符，位置；例如:a,2n"); scanf(" %c,%d",&ch,&loc); /输入要插入的元素和插入的位置 temp=insert(S,loc,ch); /插入 if(temp=False) printf("插入失败!n"); /插

9、入失败 else printf("插入成功!n"); print(S); /插入成功 break; case '3':printf("请输入要删除元素的位置:"); scanf("%d",&loc); /输入要删除的元素的位置 temp=del(S,loc,ch); /删除 if(temp=True) printf("删除了一个元素:%cn",ch); /删除成功 else printf("该元素不存在!n"); /删除失败 print(S); break; case &

10、#39;4':printf("请输入要查找的元素:"); scanf(" %c",&ch); /输入要查找的元素 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 &a

11、mp;v)/初始化线性表 int i; printf("请输入初始线性表长度：n="); /输入线性表初始化时的长度 scanf("%d",&v.last); printf("请输入从1到%d的各元素(字符)，例如:abcdefgn",v.last); getchar(); for(i=0;i<v.last;i+) scanf("%c",&v.elemi); /输入线性表的各元素BOOL insert(sqlist &v,int loc,char ch) /插入一个元素，成功返回Tru

12、e，失败返回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.elemi+1=v.elemi;/其后元素依次后移 v.elemloc-1=ch; /插入元素 v.last+; /线性表长度加一 return True; BOOL de

13、l(sqlist &v,int loc,char &ch) /删除一个元素，成功返回True，并用ch返回该元素值，失败返回False int j; if(loc<1|loc>v.last) /删除位置不合理 return False; else ch=v.elemloc-1; /ch取得该元素值 for(j=loc-1;j<v.last-1;j+) v.elemj=v.elemj+1; /其后元素依次前移 v.last-; /线性表长度减一 return True; int locate(sqlist v,char ch)/在线性表中查找ch的位置，成功返回

14、其位置，失败返回-1 int i=0; while(i<v.last&&v.elemi!=ch) i+; /当前位置后移，直到找到为止 if(v.elemi=ch) /找到当前元素 return i; else return(-1);void print(sqlist v) /显示当前线性表所有元素int i; for(i=0;i<v.last;i+) printf("%c ",v.elemi); printf("n"); 2.链式线性表的建立、插入及删除。#include <conio.h>#include &l

15、t;stdio.h>#include <stdlib.h>#define LEN sizeof(LNode) /定义LEN为一个节点的长度enum BOOLFalse,True; /定义BOOL型typedef struct nodechar data; /数据域 struct node *next;/指向下一个节点的指针LNode,*LinkList;void CreatList(LinkList &,int); /生成一个单链表BOOL ListInsert(LinkList &,int,char); /在单链表中插入一个元素BOOL ListDelete

16、(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");

17、 printf("可以进行插入，删除，定位，查找等操作。n"); printf("请输入初始时链表长度:"); /输入生成单链表时的元素个数 scanf("%d",&num); CreatList(L,num); /生成单链表 ListPrint(L); while(flag) printf("请选择:n"); printf("1.显示所有元素n"); /显示链表元素 printf("2.插入一个元素n"); /插入链表元素 printf("3.删除一个元素

18、n"); /删除链表元素 printf("4.按关键字查找元素n"); /按关键字查找 printf("5.按序号查找元素n"); /按序号查找 printf("6.退出程序 n"); /退出 scanf(" %c",&j); switch(j)case '1':ListPrint(L); break; case '2':printf("请输入元素(一个字符)和要插入的位置:n"); printf("格式:字符，位置；例如:a,3n&q

19、uot;); scanf(" %c,%d",&ch,&loc); /输入要插入的元素和要插入的位置 temp=ListInsert(L,loc,ch); /插入 if(temp=False) printf("插入失败!n"); /插入失败 else printf("插入成功!n"); /成功插入 ListPrint(L); break; case '3':printf("请输入要删除的元素所在位置:"); scanf("%d",&loc); /输入要删除的

20、节点的位置 temp=ListDelete(L,loc,ch); /删除 if(temp=False) printf("删除失败!n"); /删除失败 else printf("成功删除了一个元素:%cn",ch); /删除成功，显示该元素 ListPrint(L); break; case '4':if(L->next=NULL) /链表为空 printf("链表为空!n"); elseprintf("请输入要查找的元素(一个字符):"); scanf(" %c",&am

21、p;ch); /输入要查找的元素 temp=ListFind_keyword(L,ch,loc); /按关键字查找 if(temp=False) printf("没有找到该元素!n"); /查找失败 else printf("该元素在链表的第%d个位置。n",loc); /成功查找，显示该元素位置 break; case '5':if(L->next=NULL) /链表为空 printf("链表为空!n"); elseprintf("请输入要查找的位置:"); scanf("%d&q

22、uot;,&loc); /输入要查找的元素的位置 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 &v,int n)/生成一个带头结点的有n个元素的单链表 int

23、 i; LinkList p; v=(LinkList)malloc(LEN); /生成头结点 v->next=NULL; printf("请输入%d个字符：例如：abcdefgn",n); getchar(); for(i=n;i>0;-i) p=(LinkList)malloc(LEN); /生成新结点 scanf("%c",&p->data); p->next=v->next; v->next=p; BOOL ListInsert(LinkList &v,int i,char e)/在单链表的第i

24、各位置插入元素e，成功返回True，失败返回False LinkList p,s; int j=0; p=v; while(p&&j<i-1) p=p->next;+j; /查找第i-1个元素的位置 if(!p|j>i-1) return False; /没有找到 s=(LinkList)malloc(LEN); /生成一个新结点 s->data=e; s->next=p->next; /将新结点插入到单链表中 p->next=s; return True;BOOL ListDelete(LinkList &v,int i,ch

25、ar &e)/在单链表中删除第i个元素，成功删除返回True，并用e返回该元素值，失败返回False LinkList p,q; int j=0; p=v; while(p->next&&j<i-1) /查找第i-1个元素位置 p=p->next;+j; if(!(p->next)|j>i-1) return False; /查找失败 q=p->next;p->next=q->next; /删除该元素 e=q->data; /e取得该元素值 free(q); /释放该元素空间 return True;BOOL Lis

26、tFind_keyword(LinkList v,char e,int &i)/在单链表中查找关键字为e的元素，成功返回True,并用i返回该元素位置， /失败返回False i=1; LinkList p; p=v->next; while(p->data!=e)&&(p->next!=NULL)/p指针指向下一个，直到 p=p->next; i+; /找到或到链表尾为止 if(p->data!=e) /该元素在链表中不存在 return False; else return True;BOOL ListFind_order(LinkLi

27、st v,char &e,int i)/在单链表中查找第i个元素，成功返回True，并用e返回该元素值， /失败返回False LinkList p; int j=0; p=v; while(p->next&&j<i) /移动指针，直到找到第i个元素 p=p->next;+j; if(j!=i) return False; /查找失败 else e=p->data; /查找成功，用e取得该元素值 return True; void ListPrint(LinkList v) /显示链表所有元素 LinkList q; q=v->next;

28、printf("链表所有元素:"); while(q!=NULL) printf("%c ",q->data);q=q->next; printf("n");实验二 栈和队列一、实验目的1. 掌握栈的顺序表示和实现2. 掌握队列的链式表示和实现二、实验内容1. 编写一个程序实现顺序栈的各种基本运算。2. 实现队列的链式表示和实现。三、实验步骤1. 初始化顺序栈2. 插入元素3. 删除栈顶元素4. 取栈顶元素5. 遍历顺序栈6. 置空顺序栈7. 初始化并建立链队列8. 入链队列9. 出链队列10. 遍历链队列四、实现提示1.

29、 /*定义顺序栈的存储结构*/typedef struct      ElemType stackMAXNUM;     int top;SqStack; /*初始化顺序栈函数*/void InitStack(SqStack *p) q=(SqStack*)malloc(sizeof(SqStack) /*申请空间*/)/*入栈函数*/void Push(SqStack *p,ElemType x) if(p->top<MAXNUM-1)     p->to

30、p=p->top+1;     /*栈顶+1*/      p->stackp->top=x;   /*数据入栈*/*出栈函数*/ElemType Pop(SqStack *p)x=p->stackp->top; /*将栈顶元素赋给x*/p->top=p->top-1; /*栈顶-1*/*获取栈顶元素函数*/ElemType GetTop(SqStack *p) x=p->stackp->top;/*遍历顺序栈函数*/void OutStac

31、k(SqStack *p) for(i=p->top;i>=0;i-)printf("第%d个数据元素是：%6dn",i,p->stacki);/*置空顺序栈函数*/void setEmpty(SqStack *p) p->top= -1;2. /*定义链队列*/typedef struct Qnode   ElemType data;     struct Qnode *next;Qnodetype;typedef struct   Qnodetype *front;&

32、#160;    Qnodetype *rear;Lqueue; /*初始化并建立链队列函数*/void creat(Lqueue *q)    h=(Qnodetype*)malloc(sizeof(Qnodetype); /*初始化申请空间*/     h->next=NULL;     q->front=h;     q->rear=h;for(i=1;i<=n;i+)*利用循环快速输入数据*/&

33、#160;         scanf("%d",&x);            Lappend(q,x);   /*利用入链队列函数快速输入数据*/*入链队列函数*/void Lappend(Lqueue *q,int x) s->data=x;     s->next=NULL;   

34、  q->rear->next=s;     q->rear=s;/*出链队列函数*/ElemType Ldelete(Lqueue *q) p=q->front->next;     q->front->next=p->next;     if(p->next=NULL)     q->rear=q->front;    

35、; x=p->data;     free(p); /*释放空间*/*遍历链队列函数*/void display(Lqueue *q) while(p!=NULL)  /*利用条件判断是否到队尾*/          printf("%d->",p->data);            p=p->next;

36、0;    五、思考与提高1. 读栈顶元素的算法与退栈顶元素的算法有何区别？2. 如果一个程序中要用到两个栈，为了不发生上溢错误，就必须给每个栈预先分配一个足够大的存储空间。若每个栈都预分配过大的存储空间，势必会造成系统空间紧张。如何解决这个问题？（1）链栈只有一个top指针，对于链队列，为什么要设计一个头指针和一个尾指针？（2）一个程序中如果要用到两个栈时，可通过两个栈共享一维数组来实现。即双向栈共享邻接空间。如果一个程序中要用到两个队列，能否实现？如何实现？六、完整参考程序 1. 栈的顺序表示和实现#include <stdio.h>#includ

37、e <stdlib.h>#include <conio.h>#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2typedef int Status;typedef int SElemType;/- 栈的顺序存储表示 -#define STACK_INIT_SIZE 100#define STACKINCREMENT 10typedef struct SElemType *base; SElemType *top; int stac

38、ksize; SqStack;Status InitStack(SqStack &S);Status DestroyStack(SqStack &S);Status StackDisplay(SqStack &S);Status GetTop(SqStack S,SElemType &e);Status Push(SqStack &S,SElemType e);Status Pop(SqStack &S,SElemType &e);Status StackEmpty(SqStack S);Status InitStack(SqStack

39、&S)/构造一个空栈SS.base = (SElemType *) malloc(STACK_INIT_SIZE*sizeof(SElemType);if(!S.base) exit(OVERFLOW); /存储分配失效S.top = S.base;S.stacksize = STACK_INIT_SIZE;return OK;/InitStackStatus DestroyStack(SqStack &S)/销毁栈Sif(S.base) free(S.base);S.top = S.base = NULL;return OK;/InitStackStatus StackDis

40、play(SqStack &S)/显示栈SSElemType * p=S.base;int i = 0;if(S.base = S.top) printf("堆栈已空!n"); return OK;while( p < S.top)printf("%d:%d",+i,*p+);printf("n");return OK;/StackDisplayStatus GetTop(SqStack S,SElemType &e) /若栈不空，则用e返回S的栈顶元素，/并返回OK；否则返回ERRORif(S.top=S.ba

41、se) return ERROR;e=*(S.top-1);return OK;/GetTopStatus Push(SqStack &S,SElemType e)/插入元素e为新的栈顶元素if(S.top-S.base>=S.stacksize)/栈满，追加存储空间S.base=(SElemType*) realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType);if( ! S.base ) exit(OVERFLOW);/存储分配失败S.top = S.base + S.stacksize;S.stacksize

42、 += STACKINCREMENT;* S.top + = e;return OK;/PushStatus Pop(SqStack &S,SElemType &e)/若栈不为空，则删除S的栈顶元素，/用e返回其值，并返回OK；否则返回ERROR if (S.top = S.base) return ERROR; e = * -S.top; return OK;/PopStatus StackEmpty(SqStack S)/若S为空栈，则返回TRUE，否则返回FALSE。if(S.top = S.base) return TRUE;else return FALSE;/ St

43、ackEmptyvoid main()SqStack St;Status temp;int flag=1,ch;int e;printf("本程序实现顺序结构的堆栈的操作。n");printf("可以进行入栈，出栈，取栈顶元素等操作。n");InitStack(St); /初始化堆栈Stwhile(flag)printf("请选择:n");printf("1.显示栈中所有元素 n");printf("2.入栈 n");printf("3.出栈 n");printf("

44、;4.取栈顶元素 n");printf("5.退出程序 n");scanf("%d",&ch);switch(ch)case 1:StackDisplay(St);break;case 2:printf("请输入要入栈的元素(一个整数):");scanf("%d",&e); /输入要入栈的元素temp=Push(St,e); /入栈if(temp!=OK) printf("堆栈已满!入栈失败!n");else printf("成功入栈!n"); /成

45、功入栈StackDisplay(St);break;case 3:temp=Pop(St,e); /出栈if(temp=ERROR) printf("堆栈已空!n"); else printf("成功出栈一个元素:%dn",e); /成功出栈StackDisplay(St);break;case 4:temp=GetTop(St,e); /取得栈顶元素if(temp=ERROR) printf("堆栈已空!n");else printf("栈顶元素是:%dn",e); /显示栈顶元素break;default:fl

46、ag=0;printf("程序结束，按任意键退出!n");getch();DestroyStack(St);2. 队列的链式表示和实现#include <conio.h>#include <stdio.h>#include <stdlib.h>#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2/Status 是函数的类型,其值是函数结果状态代码typedef int Status;/ElemType

47、 是顺序表数据元素类型,此程序定义为int型typedef int QElemType;/-单链队列-队列的链式存储结构-typedef struct QNode /定义结点结构QElemType data; /数据域struct QNode *next; /指针域QNode,*QueuePtr;typedef struct linkqueue /定义队列结构QueuePtr front; /队头指针QueuePtr rear; /队尾指针LinkQueue;Status InitLinkQueue(LinkQueue &); /初始化一个队列Status DestroyLinkQue

48、ue(LinkQueue &); /销毁一个队列int LinkQueueLength(LinkQueue &Q); /队列的长度Status EnLinkQueue(LinkQueue &,QElemType); /将一个元素入队列Status DeLinkQueue(LinkQueue &,QElemType &);/将一个元素出队列Status DisplayLinkQueue(LinkQueue); /显示队列中所有元素void main()LinkQueue LQ;QElemType e;int flag=1,ch,len;Status tem

49、p;printf("本程序实现链式结构队列的操作。n");printf("可以进行入队列、出队列等操作。n");InitLinkQueue(LQ); /初始化队列while(flag)printf("请选择:n");printf("1.显示队列所有元素n");printf("2.入队列n");printf("3.出队列n");printf("4.求队列的长度n");printf("5.退出程序n");scanf("%d&quo

50、t;,&ch);switch(ch)case 1:DisplayLinkQueue(LQ); /显示队列中所有元素break;case 2:printf("请输入要人队的元素(一个整数):");scanf("%d",&e); /输入要入队列的字符EnLinkQueue(LQ,e);/入队列DisplayLinkQueue(LQ);break;case 3:temp=DeLinkQueue(LQ,e); /出队列if(temp=OK)printf("出队一个元素:%dn",e);DisplayLinkQueue(LQ);

51、else printf("队列为空!n");break;case 4:len=LinkQueueLength(LQ);printf("队列的长度为:%dn",len);break;default:flag=0;printf("程序运行结束，按任意键退出!n");getch();Status InitLinkQueue(LinkQueue &Q)/队列初始化Q.front=Q.rear=(QueuePtr) malloc(sizeof(QNode); /生成一个头结点，并把首尾指针指向头结点Q.front->next=NU

52、LL;return OK;Status DestroyLinkQueue(LinkQueue &Q)/销毁一个队列QueuePtr p;QElemType e;while(Q.front!=Q.rear)DeLinkQueue(Q,e);free(Q.front);Q.front=Q.rear=NULL;return OK;int LinkQueueLength(LinkQueue &Q)/队列的长度int i=0;QueuePtr p=Q.front;while(p!=Q.rear)+i;p=p->next;return i;Status EnLinkQueue(Lin

53、kQueue &Q,QElemType e)/入队列QueuePtr p;p=(QueuePtr)malloc(sizeof(QNode);/生成一个新结点p->data=e; /赋值p->next=NULL;Q.rear->next=p; /插入至队列尾Q.rear=p; /修改队尾指针return OK;Status DeLinkQueue(LinkQueue &Q,QElemType &e)/出队列QueuePtr p;if(Q.front=Q.rear) return ERROR; /判断队列是否已空，已空返回ERRORp=Q.front-&g

54、t;next; /p指向队列中第一个元素e=p->data; /取得该元素值Q.front->next=p->next; /修改队首指针if(Q.rear=p) Q.rear=Q.front; /若队列已空，把队尾指针指向头结点return OK; /成功出队列，返回OKStatus DisplayLinkQueue(LinkQueue Q)/显示队列中所有元素QueuePtr p;int i=0;p=Q.front->next;if(p=NULL) printf("队列为空!n");/队列为空elsewhile(p) /否则显示队列中所有元素pri

55、ntf("%d:%d",+i,p->data);p=p->next;printf("n");return OK;实验三 数组和广义表一、实验目的1. 掌握稀疏矩阵的压缩存储2. 掌握稀疏矩阵的转置算法二、实验内容1. 实现上三角阵的压缩存储。2. 用三元组顺序表存储稀疏矩阵，并实现矩阵的转置。三、实验步骤1. 创建一个数组。2. 输入数据3. 给定矩阵任一元素的下标，4. 打印给定下标所对应的数据。5. 创建三元组顺序表。6. 输入矩阵中的数据。7. 输出对应的矩阵。四、实现提示1.对于如下对称矩阵：将它们存入到一个线性数组中B，不存非零元素，a11存入到第1个位置，a21存入到第二个位置，则aij能存到第几个位置，我们要以用梯形公式算面积。aij的位置是它上面的元素之和再加上左边的元素之和。它上面的元素之和为(1+(i-1)×(i-1)/2，左边的元素为(j-1)所以这个元素存储的位置为k=i(i-1)/2+j-1。因为矩阵A为对称矩阵