1.实验要求
1.1掌握数据结构中线性表的基本概念。
1.2熟练掌握线性表的基本操作：创建、插入、删除、查找、输出、求长度及合并并运算在顺序存储结构上的实验。
1.3熟练掌握链表的各种操作和应用。
2.实验内容
2.1编写一个函数，从一个给定的顺序表A中删除元素值在x到y之间的所有元素，要求以较高效率来实现。
2.2试写一个算法，在无头结点的动态单链表上实现线性表插入操作
2.3设计一个统计选票的算法，输出每个候选人的得票结果。
3.实验代码
2.1代码：
#include typedef int elemtype; #define maxsize 10 int del(int A[],int n,elemtype x,elemtype y) { int i=0,k=0; while(i k++; else A[i-k]=A[i]; i++; } return(n-k); } void main() { int i,j; int a[maxsize]; printf("输入%d个数:\\n",maxsize); for(i=0;i j=del(a,maxsize,1,3); printf("输出删除后剩下的数:\\n"); for(i=0;i } 2.2代码： INSERT(L,i,b)。 void Insert(Linklist &L,int i,elemtype x) { if(!L) { L=(Linklist)malloc(sizeof(Lnode)); (*L).data=x;(*L).next=NULL; } else { if(i==1) { s=(Linklist)malloc(sizeof(Lnode)); s->data=x;s->next=L;L=s; } else { p=L;j=1; while(p&&j if(p||j>i-1) return error; s=(Linklist)malloc(sizeof(Lnode)); s->data=x;s->next=p->next;p->next=s; } } } 2.3代码： typedef int elemtype typedef struct linknode { elemtype data; struct linknode *next; }nodetype; nodetype *create() { elemtype d; nodetype h=NULL,*s,*t; int i=1; printf("建立单链表:\\n"); while(1) { printf("输入第%d个结点数据域",i); scanf("%d",&d); if(d==0)break; if(i==1) { h=(nodetype *)malloc(sizeof(nodetype)); h->data=d;h->next=NULL;t=h; } else { s=(nodetype *)malloc(sizeof(nodetype)); s->data=d;s->next=NULL;t->next=s; t=s; } i++; } return h; } void sat(nodetype *h,int a[]) { nodetype *p=h; while(p!=NULL) { a[p->data]++; p=p->next; } } void main() { int a[N+1],i; for(i=0;i nodetype *head; head=create(); sat(head,a); printf("候选人:"); for(i=1;i<=N;i++) printf("%3d",i); printf("\\n得票数\\n"); for(i=1;i<=N;i++) printf("%3d",a[i]); printf("\\n"); } 4.实验小结 线性表是最简单的、最常用的一种数据结构，是实现其他数据结构的基础。 实验二 栈与队列 1.实验要求 1.1了解栈和队列的特性，以便灵活运用。 1.2熟练掌握栈和有关队列的各种操作和应用。 2.实验内容 2.1设一个算术表达式包括圆括号，方括号和花括号三种括号，编写一个算法判断其中的括号是否匹配。 3.实验代码 2.1代码： #include #include #include #define NULL 0 typedef struct list { char str; struct list *next; }list; void push(char,list *); int pop(char.list *); void deal(char *str); main(void) { char str[20]; printf("\\n请输入一个算式:\\n"); gets(str); deal(str); printf("正确!"); getchar(); return 0; } void deal(char *str) { list *L; L=(list *)malloc(sizeof(list)); if(!L) { printf("错误!"); exit(-2); } L->next=NULL; while(*str) { if(*str=='('||*str=='['||*str=='{') push(*str,L); else if(*str==')'||*str==']'||*str=='}') if(pop(*str,L)) {puts("错误,请检查!"); puts("按回车键退出"); getchar();exit(-2); } str++; } if(L->next) { puts("错误,请检查!"); puts("按任意键退出"); getchar();exit(-2); } } void push(char c,list *L) { list *p; p=(list *)malloc(sizeof(list)); if(!p) { printf("错误!"); exit(-2); } p->str=c; p->next=L->next; L->next=p; } #define check(s) if(L->next->str==s){p=l->next;L->next=p->next;free(p);return(0);} int pop(char c,list *L) { list *p; if(L->next==NULL)return 1; switch(c) { case')':check('(') break; case']':check('[') break; case'}':check('{') break; } return 1; 4.实验小结 栈和队列是最基础的一种数据结构之一，为实现其他数据结构的奠定基石。 实验三 树 1.实验要求 1.1掌握二叉树，二叉树排序数的概念和存储方法。 1.2掌握二叉树的遍历算法。 1.3熟练掌握编写实现树的各种运算的算法。 2.实验内容 2.1编写程序，求二叉树的结点数和叶子数。 2.2编写递归算法，求二叉树中以元素值为X的结点为根的子数的深度。 2.3编写程序，实现二叉树的先序，中序，后序遍历，并求其深度。 3.实验代码 2.1代码： #include #include struct node{ char data; struct node *lchild,*rchild; }bnode; typedef struct node *blink; blink creat() { blink bt; char ch; ch=getchar(); if(ch==' ') return(NULL); else { bt=(struct node *)malloc(sizeof(bnode)); bt->data=ch; bt->lchild=creat(); bt->rchild=creat(); } return bt; } int n=0,n1=0; void preorder(blink bt) { if (bt) { n++; if(bt->lchild==NULL&&bt->rchild==NULL) n1++; preorder(bt->lchild); preorder(bt->rchild); } } void main() { blink root; root=creat(); preorder(root); printf("此二叉数的接点数有:%d\\n",n); printf("此二叉数的叶子数有:%d\\n",n1);} 2.2代码： int get_deep(bitree T,int x) { if(T->data==x) { printf("%d\\n",get_deep(T)); exit 1; } else { if(T->lchild)get_deep(T->lchild,x); if(T->rchild)get_deep(T->rchild,x); } int get_depth(bitree T) { if(!T)return 0; else { m=get_depth(T->lchild); n=get_depth(T->rchild); return(m>n?m:n)+1; } } 2.3代码： #include #include struct node{ char data; struct node *lchild,*rchild; }bnode; typedef struct node *blink; blink creat() { blink bt; char ch; ch=getchar(); if(ch==' ') return(NULL); else { bt=(struct node *)malloc(sizeof(bnode)); bt->data=ch; bt->lchild=creat(); bt->rchild=creat(); } return bt; } void preorder(blink bt) { if (bt) { printf("%c",bt->data); preorder(bt->lchild); preorder(bt->rchild); } } void inorder(blink bt) { if(bt) { inorder(bt->lchild); printf("%c",bt->data); inorder(bt->rchild); } } void postorder(blink bt) { if(bt) { postorder(bt->lchild); postorder(bt->rchild); printf("%c",bt->data); } } int max(int x,int y) { if(x>y) return x; else return y; } int depth(blink bt) { if (bt) return 1+max(depth(bt->lchild),depth(bt->rchild)); else return 0; } void main() { blink root; root=creat(); printf("\\n"); printf("按先序排列:"); preorder(root);printf("\\n"); printf("按中序排列:"); inorder(root);printf("\\n"); printf("按后序排列:"); postorder(root);printf("\\n"); printf("此二叉数的深度是:"); printf("depth=%d\\n",depth(root)); } 4.实验小结 通过本章学习实验，对树有了初步的认识。树就是一种非线性的数据结构，描述了客观世界中事物之间的层次关系。这种结构有着广泛的应用，一切具有层次关系的问题都可以用树来表示。 实验四 图 1.实验要求 1.1熟悉图的各种存储方法。 1.2掌握遍历图的递归和非递归的算法。 1.3理解图的有关算法。 2.实验内容 2.1写出将一个无向图的邻接矩阵转换成邻接表的算法。 2.2以邻接表作存储结构，给出拓扑排序算法的实现。 3.实验代码 2.1代码： void mattolist(int a[][],adjlist b[],int n) /*n为图的结点个数*/ { for(i=0;i if(a[i][j]!=0) {p=(arcnodetp *)malloc(sizeof(arcnodetp));/*产生邻接点*/ p->adjvex=j; p->nextare=b[i].firstare; b[i].firstarc=p; } } 2.2代码： typedef struct vexnode { VertexType vertex; int in;/*增加一个入度域*/ ArecNodeTp * fristarc; }AdjList[vnum]; typedef struct graph { AdjList adjlist; int vexnum,arcnum; }GraphTp; Top_Sort(GraphTp g) { LstackTp *p;/*建立入度为0的顶点栈S*/ int m,i,v; initStack(S); for(i=0;i push(S,&v);/*w入S栈*/ m=0; whlie(!EmptyStack(S)){ Pop(S,&v)//S出栈->v printf("%d",v);/*输出v*/ m++; p=g.adjlist[i].fristarc;/*p=图g中顶点v的第一个邻接点*/ while(p!=NULL){//p存在 (g.adjlist[p->adjvex].in)--;/*p的入度--*/ if(g.adjlist[p->adjvex].in==0)/*if(p的入度==0)*/ Push(S,p->adjvex);/*p入S栈*/ p=p->nextarc;/*p=图g中的顶点v的下一个邻接点*/ } } if(m } 4.实验小结 通过本章学习实验，对图有了具体的认识。图也是一种非线性的数据结构，这种结构有着广泛的应用，一切具有关系的问题都可以用图来表示。 实验五 查找 1.实验要求 1.1掌握顺序查找、二分法查找、分块查找和哈希表查找的算法。 1.2能运用线性表的查找方法解决实际问题。 2.实验内容 2.1编写一个算法，利用二分查找算法在一个有序表中插入一个元素X，并保持表的有序性。 2.2根据给定的数据表，先建立索引表，然后进行分块查找。 3.实验代码 2.1代码： #include #include #define MAXNUM 20 int input(int *);/*输入数据*/ int search(int *,int,int);/*查找插入位置*/ void plug(int *,int,int);/*插入数据*/ void main(void) { int data[MAXNUM],m; int insert=1; m=input(data); printf("Input the insert num:"); scanf("%d",data); insert=search(data,1,m);/*返回插入位置*/ plug(data,insert,m); for(insert=1;insert<=m+1;insert++)/*显示数据*/ printf("%3d",*(data+insert)); getch(); } int input(int *data) { int i,m; printf("\\nInput the max num:"); scanf("%d",&m); printf("input data\\n"); for(i=1;i<=m;i++) scanf("%d",data+i); return m; } int search(int *data,int low,int high)/*递归查找插入位置*/ { int mid; if(low>high) return low;/*没有找到插入数据，返回low*/ else{ mid=(low+high)/2; if(*(data+mid)==*data) retun mid;/*找到插入数据，返回mid*/ else if(*(data+mid)<*data) else if(*()data+mid)>*data) } search(data,low,high); } void plug(int *data,int insert,int m) { int i; for(i=m;i>insert;i--) *(data+i+1)=*(data+i); *(data+insert)=*data } 2.2代码： #include #include #include #definr N 18 /*元素个数*/ #definr Blocknum 3 /*分块数*/ typedef struct indexterm { int key;/*最大关键字*/ int addr;/*块的起始地址*/ }index; /*索引表数据类型*/ index * CreateList(int data[],int n)/*建索引表*/ { index *p; int m,j,k; m=n/BlockNum;/*分为BlockNum块，每块有m个元素*/ p=(index *)malloc(BlockNum *sizeof(index)); for(k=0;k (p+k)->addr=m*k; for(j=m*k;j (p+k)->key=data[j];/*块的最大关键字*/ } return p; } int BlockSearch(index *list,int rectab[],int n,int m,int k)/*分块查找*/ { int low=0,high=m-1,mid,i; int b=n/m;/*每块有b个元素*/ while(low<=high){/*块间折半查找*/ mid=(low+high)/2; if((list+mid)->key>=k) high=mid+1; else low=mid+1; } if(low if(i<=(list+low)->addr+b-1) return i; else return -1; } return -1; } void main() { int record[N]={22,12,13,8,9,20,33,42,44,38,24,48,60,58,74,49,86,53}; int key; index *list; printf("please input key:\\n"); scanf("%d",&key); list=CreateList(record,N); printf("data postion id %d\\n",BlockSearch(list,record,N,BlockNum,key)); } 4.实验小结 通过本章的学习，对排序有较高层次的理解与认识，从平时的练习中可以看出排序是数据处理中经常用到的重要运算。有序的顺序表可以采用查找效率较高的折半查找法，而无序的顺序表只能用效率较低的顺序查找法。下载本文
