《数据结构实验一-线性表及其应用实验二-栈和队列的应用实验三-树和二叉树的建立和应用（1）》由会员分享，可在线阅读，更多相关《数据结构实验一-线性表及其应用实验二-栈和队列的应用实验三-树和二叉树的建立和应用（1）（63页珍藏版）》请在金锄头文库上搜索。
1、DONGFANG COLLEGE，FUJIAN AGRICULTURE AND FORESTRY UNIVERSITY课程名称：数据结构系 别：计算机系年级专业：2010级电子信息工程学 号： 1050302103姓名： 廖少兵任课教师： 谢储辉成绩：2012年12月25日实验一 线性表及其应用【实验目的】1. 熟练掌握线性表的基本操作在顺序存储和链式存储上的实现；2. 以线性表的各种操作（建立、插入、删除、遍历等）的实现为重点；3. 掌握线性表的动态分配顺序存储结构的定义和基本操作的实现；4. 通过本章实验帮助学生加深对 C 语言的使用（特别是函数的参数调用、指针类型的应用和链表的建立等各种
2、基本操作）。【实验内容】1 线性表顺序存储的基本操作参考程序：/*线性表顺序存储的基本操作*/#include <stdio.h>#define MaxSize 50typedef char ElemType;struct ListElemType listMaxSize;int size;void setnull(struct List *p)p->size=0;int length(struct List *p)return(p->size);int get(struct List *p,int i)if (i>p->size)return(-1);el
3、sereturn(p->listi-1);int locate(struct List *p,ElemType x)int i=0;while (i<p->size && p->listi!=x) i+;if (i=p->size)return(-1);elsereturn(i+1);void insert(struct List *p,ElemType x,int i)int j;if (i<1 && i>p->size+1)printf("位置参数不正确,不能进行插入操作!n");elsep
4、->size+;for (j=p->size-1;j>=i;j-) /*结点向后移动,腾出一个位置*/p->listj=p->listj-1;p->listj=x;void delete(struct List *p,int i)int j;if (i>p->size | i<1)printf("位置参数不正确,不能进行删除操作!n");elsefor (j=i-1;j<p->size-1;j+) /*结点向前移动,覆盖该删除的结点*/p->listj=p->listj+1;p->size-
5、;display(struct List *p)int j;if (p->size=0)printf("该线性表为空,不能显示!n");elseprintf("线性表:");if (p->size=1) /*只有一个结点的情况*/printf("%c",p->listp->size);else /*有一个以上结点的情况*/for (j=0;j<p->size-1;j+)printf("%c",p->listj);printf("%c",p->lis
6、tj); /*显示最后一个结点*/printf("n");main()struct List L;setnull(&L);insert(&L,'a',1);insert(&L,'b',2);insert(&L,'a',1);insert(&L,'c',2);insert(&L,'d',1);insert(&L,'e',2);display(&L);printf("值:%c 位置:%dn",'
7、;a',locate(&L,'a');printf("位置:%d 值:%cn",4,get(&L,4);printf("删除第 2 个结点后");delete(&L,2);display(&L);printf("删除第 2 个结点后");delete(&L,2);display(&L);printf("删除第 1 个结点后");delete(&L,1);display(&L);printf("删除第 1 个结点后&qu
8、ot;);delete(&L,1);display(&L);2 线性表链式存储的基本操作/*线性表链式存储-单链表的基本操作*/#include <stdio.h>#include <malloc.h>typedef char ElemType;struct LNodeElemType data;struct LNode *next;setnull(struct LNode *p)*p=NULL;int length(struct LNode *p)int n=0;struct LNode *q=*p;while (q!=NULL)n+;q=q->
9、next;return(n);ElemType get(struct LNode *p,int i)int j=1;struct LNode *q=*p;while (j<i && q!=NULL) /*查找第 i 个结点*/q=q->next;j+;if (q!=NULL) /*找到了第 i 个结点*/return(q->data);elseprintf("位置参数不正确!n");int locate(struct LNode *p,ElemType x)int n=0;struct LNode *q=*p;while (q!=NULL
10、&& q->data!=x) /*查找data 域为 x 的第一个结点*/q=q->next;n+;if (q=NULL) /*未找到 data 域等于 x 的结点*/return(-1);else /*找到data 域等于 x 的结点*/return(n+1);void insert(struct LNode *p,ElemType x,int i)int j=1;struct LNode *s,*q;s=(struct LNode *)malloc(sizeof(struct LNode); /*建立要插入的结点 s*/s->data=x;q=*p;if
11、(i=1) /*插入的结点作为头结点*/s->next=q;*p=s;elsewhile (j<i-1 && q->next!=NULL) /*查找第 i-1 个结点*/q=q->next;j+;if (j=i-1) /*找到了第 i-1 个结点,由 q 指向它*/s->next=q->next; /*将结点 s 插入到 q 结点之后*/q->next=s;else printf("位置参数不正确!n");void delete(struct LNode *p,int i)int j=1;struct LNode *
12、q=*p,*t;if (i=1) /*删除链表的头结点*/t=q;*p=q->next;elsewhile (j<i-1 && q->next!=NULL) /*查找第 i-1 个结点*/q=q->next;j+;if (q->next!=NULL && j=i-1) /*找到第 i-1 个结点,由 q 指向它*/t=q->next; /*t 指向要删除的结点*/q->next=t->next; /*将q 之后的结点删除*/else printf("位置参数不正确!n");if (t!=NULL
13、) /*在 t 不为空时释放该结点*/free(t);void display(struct LNode *p)struct LNode *q;q=*p;printf("单链表显示:");if (q=NULL) /*链表为空时*/printf("链表为空!");else if (q->next=NULL) /*链表只有一个结点时*/printf("%cn",q->data);else /*链表存在一个以上的结点时*/while (q->next!=NULL) /*显示前面的结点*/printf("%c&qu
14、ot;,q->data);q=q->next;printf("%c",q->data); /*显示最后一个结点*/printf("n");main()struct LNode *head;setnull(&head);insert(&head,'a',1);insert(&head,'b',2);insert(&head,'a',2);insert(&head,'c',4);insert(&head,'d',3
15、);insert(&head,'e',1);display(&head);printf("单链表长度=%dn",length(&head);printf("位置:%d 值:%cn",3,get(&head,3);printf("值:%c 位置:%dn",'a',locate(&head,'a');printf("删除第 1 个结点:");delete(&head,1);display(&head);printf(
16、"删除第 5 个结点:");delete(&head,5);display(&head);printf("删除开头 3 个结点:");delete(&head,3);delete(&head,2);delete(&head,1);display(&head);3 双链表的基本操作/*双链表的基本操作*/#include <stdio.h>#include <malloc.h>typedef char ElemType;struct DNodeElemType data;struct DNode *left,*right;setnull(struct DNode *p)*p=NULL;int length(struct DNode *p)int n=0;struct DNode *q=*p;while (q!=NULL)n+;q=q->right;return(n);ElemType get(struct DNode *p,int i)int j=1;struct DN
