数据结构实验讲义(C语言版).doc

数据结构实验计算机科学与技术系复习实验目的：1. 熟悉编程环境；2. 复习C语言程序设计的基本内容。实验内容：1.在一维数组的第i个元素之前插入一个元素； 2. 在一维数组中删除第i个元素。实验一：线性表的顺序存储结构实验目的：1.帮助学生熟练掌握线性表的操作在顺序存储结构上的实现。 2.使学生掌握顺序表的一些应用。实验内容：该程序的功能是对元素类型为整型的顺序表进行一些操作。该程序包括顺序表结构类型的定义以及对顺序表操作的具体的函数定义和主函数注意事项:在做第一次“数据结构”课程实验之前，要在硬盘上建立好自己的工作目录，专门来存储你所做的实验程序及相关信息，以后每次做实验都采用这个目录。程序源代码：/* 定义ElemType为int类型 */typedef int ElemType;/*顺序表存储空间的总分配量*/#define MAXSIZE 100#define FALSE 0#define TRUE 1/* 顺序存储类型 */typedef structElemType dataMAXSIZE; /*存放线性表的数组*/ int length; /* length是顺序表的长度*/SeqList;/* 初始化顺序表 */SeqList SeqListInit( )SeqList L; L.length=0; return L; /* 清空顺序表 */SeqList ListClear(SeqList L)L.length=0; return L;/* 求顺序表长度 */int ListLength(SeqList L) return(L.length);/* 检查顺序表是否为空 */int ListEmpty(SeqList L)if(L.length) return(FALSE); else return(TRUE);/*检查顺序表是否为满 */int ListFull(SeqList L)if(L.length=MAXSIZE) return(TRUE); else return(FALSE);/* 遍历顺序表 */void ListTraverse(SeqList L)int i; if(L.length=0) printf(顺序表为空n); else printf(当前顺序表中的元素为:n); for(i=1;i=L.length;i+) printf(%d ,L.datai-1); printf(n); /* 从顺序表中查找元素 */ElemType ListGet(SeqList L ,int i)ElemType e; e=L.datai-1; return(e);/* 从顺序表中查找与给定元素值相同的元素在顺序表中的位置 */int ListLocate(SeqList L, ElemType x)int i=0; while(iL.length & L.datai!=x) i+; if (iL.length) return (i+1); else return 0;/* 向顺序表中插入元素 */SeqList ListInsert(SeqList L,int i,ElemType x)int j; if(L.length=MAXSIZE) printf(表满,不能插入n); else if(iL.length+1) printf(插入位置不正确n); else for(j=L.length-1;j=i-1;j-)L.dataj+1=L.dataj; L.datai-1=x; L.length+; return L; /* 从顺序表中删除元素 */SeqList ListDelete(SeqList L,int i)int j;ElemType x; if (iL.length)printf(删除位置不正确n); else x=L.datai-1; for(j=i;j=L.length-1;j+) L.dataj-1=L.dataj; L.length-; printf(%d已被删除n,x); return L;/*求顺序表中元素的前驱*/ElemType SeqListPrior(SeqList L,ElemType e)int i=0; while(iL.length&L.datai!=e)i+; if(i=0) printf(第一个元素没有前驱n);return 0; else if(i=L.length-1) return(L.datai-1);else printf(不存在值为%d的元素n,e);return 0;/*求顺序表中元素的后继*/ElemType SeqListNext(SeqList L,ElemType e)int i=0; while(iL.length&L.datai!=e) i+; if(i=L.length-1) printf(最后一个元素没有后继n);return 0; else if(iL.length-1) return(L.datai+1);else printf(不存在值为%d的元素n,e);return 0;int scan()int d; printf(请选择所要进行的操作n); printf(1.初始化 2.清空3.求顺序表长度4.检查顺序表是否为空n); printf(5.检查顺序表是否为满 6.遍历顺序表 7.从顺序表中查找元素n); printf(8.从顺序表中查找与给定元素值相同的元素在顺序表中的位置n); printf(9.向顺序表中插入元素10. 从顺序表中删除元素n); printf(11.求元素的前驱 12.求元素的后继n); printf(其他键退出.n); scanf(%d,&d); return(d);main()int quit=0;int i,location; ElemType e,prior,next; SeqList L; printf(第一次操作需选择初始化n); while(!quit) switch(scan() case 1:L=SeqListInit();break; case 2:ListClear(L);break; case 3:printf(顺序表的长度为%dn,ListLength(L);break; case 4:if(ListEmpty(L)printf(顺序表为空n);else printf(顺序表不为空n);break; case 5:if(ListFull(L)printf(顺序表满n);else printf(顺序表不满n);break; case 6:ListTraverse(L);break; case 7:printf(请输入要查找的元素的位置n);scanf(%d,&i);if(L.length=0) printf(顺序表已空n);else if(iL.length) printf(查找的位置不正确n); else printf(顺序表中第%d个元素的值为:%dn,i,ListGet(L,i);break; case 8:printf(请输入要查找的元素的值n);scanf(%d,&e);if(L.length=0) printf(顺序表已空n);else location=ListLocate(L,e); if(location=0) printf(顺序表中不存在值为%d的元素n,e); else printf(顺序表中%d的位置是:%dn,e,ListLocate(L,e);break; case 9:printf(请输入要插入的元素的位置和其值:n);scanf(%d%d,&i,&e);L=ListInsert(L,i,e);break; case 10:printf(请输入要删除的元素的位置:n); scanf(%d,&i); L=ListDelete(L,i); break; case 11:scanf(%d,&e); prior=SeqListPrior(L,e); if(prior) printf(%d的前驱是:%dn,e,prior);break; case 12:scanf(%d,&e); next=SeqListNext(L,e); if(next) printf(%d的后继是:%dn,e,next);break; default:quit=1;实验二：线性表的链式存储结构实验目的：1.熟悉链表结构；2.掌握链表结构上的各种操作；3.学会运用链表结构求解问题。实验内容：建立一个单链表,在此单链表上实现以下几种操作: 1、求此单链表的长度； 2、在此单链表的第i个元素结点之前插入一个结点； 3、删除此单链表的第i个元素结点。程序源代码：/* 定义ElemType为int类型 */typedef int ElemType;#define TRUE 1#define FALSE 0#define NULL 0#define flag -1/* 单链表的结点类型 */typedef struct LNodeElemType data; struct LNode *next; LNode,*LinkedList;/* 初始化单链表 */LinkedList LinkedListInit()LinkedList L; L=(LinkedList)malloc(sizeof(LNode); L-next=NULL; return L;/* 清空单链表 */void LinkedListClear(LinkedList L)L-next=NULL; printf(链表已经清空n);/* 检查单链表是否为空 */int LinkedListEmpty(LinkedList L)if(L-next=NULL) return TRUE; else return FALSE;/* 遍历单链表 */void LinkedListTraverse(LinkedList L)LinkedList p; p=L-next; if(p=NULL) printf(单链表为空表n); elseprintf(链表中的元素为:n); while(p!=NULL) printf(%d ,p-data); p=p-next; printf(n);int LinkedListLength (LinkedList L)LinkedList p; int j; p=L-next; j=0; while(p!=NULL) j+;p=p-next; return j; LinkedList LinkedListGet(LinkedList L,int i)LinkedList p;int j; p=L-next;j=1; while (p!=NULL & jnext; j+; if (j=i) return p; else return NULL;int LinkedListLocate ( LinkedList L, ElemType x)LinkedList p;int j; p=L-next; j=1; while ( p!=NULL & p-data != x) p=p-next;j+; if(p) return j; else return 0; void LinkedListInsert(LinkedList L, int i, ElemType x)LinkedList p,s; int j; j=1;p=L; while(p&jnext;j+; if(p=NULL|ji) printf(插入位置不正确n); else s=(LNode *)malloc(sizeof(LNode); s-data=x; s-next=p-next; p-next=s; printf(%d已插入到链表中n,x); void LinkedListDel(LinkedList L,int i) LinkedList p,q; int j; j=1;p=L; while(p-next&jnext;j+; if(p-next=NULL)printf(删除位置不正确n); else q=p-next;p-next=q-next;free(q); printf(第%d个元素已从链表中删除n,i); LinkedList LinkedListCreat( ) LinkedList L=LinkedListInit(),p,r; ElemType x; r=L; printf(请依次输入链表中的元素,输入-1结束n); scanf(%d,&x); while (x!=flag)p=(LinkedList)malloc(sizeof(LNode);p-data=x;r-next=p;r=p;scanf(%d,&x);r-next=NULL;return L;int scan()int d; printf(请选择要进行的操作n); printf(1.初始化 2.清空3.求链表长度4.检查链表是否为空n); printf(5.遍历链表 6.从链表中查找元素n); printf(7.从链表中查找与给定元素值相同的元素在顺序表中的位置n); printf(8.向链表中插入元素9. 从链表中删除元素n); printf(其他键退出。n); scanf(%d,&d); return(d);main()int quit=0;int i,locate;ElemType e; LinkedList L,p; while(!quit) switch(scan() case 1:L=LinkedListInit();printf(n);break; case 2:LinkedListClear(L);printf(n);break; case 3:printf(链表的长度为 %dn,LinkedListLength(L);break; case 4:if(LinkedListEmpty(L)printf(链表为空n);else printf(链表非空n);break; case 5:LinkedListTraverse(L);break; case 6:printf(请输入待查询元素在链表中的位置:);scanf(%d,&i);p=LinkedListGet(L,i);if(p)printf(链表中第%d个元素的值为:%dn,i,p-data);else printf(查询位置不正确n);break; case 7:printf(请输入待查询元素的值:);scanf(%d,&e);locate=LinkedListLocate(L,e);if(locate) printf(%d在链表中的位置是:%dn,e,locate);else printf(链表中没有值为%d的元素n,e);break; case 8:printf(请输入插入元素的位置和值(中间以空格或回车分隔):n);scanf(%d%d,&i,&e);LinkedListInsert(L,i,e);break; case 9:if(LinkedListLength(L)=0)printf(链表已经为空,不能删除n); else printf(请输入待删除元素的位置:n);scanf(%d,&i);LinkedListDel(L,i);break; case 10:L=LinkedListCreat(); printf(n);break; default:quit=1;实验三：栈和队列实验目的：1.熟悉栈和队列结构；2.掌握栈和队列结构上的各种操作；3.学会运用栈和队列结构求解问题。实验内容：1.建立一个链队列，在建立好的队列中实现以下操作 makenull：将队列置成空队列； get：返回队列的第一个元素； enqueue：把元素x插入到队列的后端； dequeue：删除队列的第一个元素； empty：判定队列是否为空。 2.栈的基本操作实现。 1、程序清单：#define null 0struct nodeint data; struct node *next;struct node *rear;struct node *creat(void)struct node *p,*front; int i,n; scanf(%d,&n); front=(struct node *)malloc(2); front-next=null; for (i=1;idata); p-next=front-next; front-next=p; rear=front; while (rear-next!=null) rear=rear-next; return(front); struct node *makenull(struct node *front) rear=front;front-next=null; return(front); int get(struct node *front) int x;x=front-next-data;return(x);struct node *enqueue(struct node *front ,int x)struct node *s; s=(struct node *)malloc(2); s-data=x; s-next=rear-next; rear-next=s ; rear=s; return(front); struct node *dequeue(struct node *front)struct node *q; q=front-next; front-next=front-next-next; free(q); return(front);int empty(struct node *front)if (front=rear) return(1); else return(0);void print(struct node *front) struct node *p; p=front; while(p-next!=null) p=p-next;printf(%d,p-data);main()int x,e,y; struct node *front; front=creat(); print(front); e=get(front);printf(“%d”,e); scanf(%d,&x); front=enqueue(front,x); print(front); front=dequeue(front); print(front); y=empty(front); printf(%d,y); makenull(front); y=empty(front); printf(%d,y); 2、程序清单：#include #include #include #include #define MAX 20#define False 0#define True 1typedef struct char elemMAX; int top; SqStack;char ch;SqStack S;void Initial(void)S.top=-1; int Push(char ch) if(S.top=MAX-1) return False; else S.top+; S.elemS.top=ch; return True; int Pop(void) if(S.top=-1) return False; else S.top-; ch=S.elemS.top+1; return True; int Gettop(void) if(S.top=-1) return False; else ch=S.elemS.top; return True; void SqStackPrint(void) int i; if(S.top=-1) printf(stack empty!n); else printf(stack all elem is:n); for(i=0;i=i;k-) sk+n2=sk; for(k=1;k=n2;k+) sk+i-1=tk; n1=n1+n2; for(k=1;k=n1;k+) printf(%c,sk); void delete(char s,int i,int j)int k; for(k=i+j;k=n1;k+) sk-j=sk; n1=n1-j; for(k=1;k=n1;k+) printf(%c,sk);main()char s10,t10; int i,j,k; scanf(%d%d,&n1,&n2); for (k=1;k=n1;k+) scanf(%c,&sk); for (k=1;kdata=c; T-Lchild=create(); T-Rchild=create(); return T;void preorder(Btree T) if(T) printf(%c ,T-data); preorder(T-Lchild); preorder(T-Rchild); void inorder(Btree T) if(T) inorder(T-Lchild); printf(%c ,T-data); inorder(T-Rchild); void postorder(Btree T) if(T) postorder(T-Lchild); postorder(T-Rchild); printf(%c ,T-data); int depth(Btree T) int dep1,dep2; if(T=null) return (0); else dep1=depth(T-Lchild); dep2=depth(T-Rchild); if (dep1dep2) return (dep1+1); else return (dep2+1); int nodesum(Btree T) if(T=null) return (0); else return (nodesum(T-Lchild)+nodesum(T-Rchild)+1); main() Btree T; T=create(); preorder(T); printf(n); inorder(T); printf(n); postorder(T); printf(n%d,depth(T); printf(n%dn,nodesum(T); 实验六：查找实验目的：1.使学生熟练掌握顺序查找算法； 2.使学生熟练掌握折半查找算法。实验内容：1.编写顺序查找和折半查找算法。 2.(选做) 建立一棵二叉排序树，实现在其中进行查找操作。程序清单：1.int n;int search_seq(int a,int key)int i=n; a0=key; while(ai!=key) i-; return(i);int search_bin(int a,int key)int l,h,m; l=0;h=n-1; while(l=h) m=(l+h)/2; if(keyam) h=m-1; else if(key=am) return(m); else l=m+1; return(-1); main()int i,