1、数据结构上机实验题目实验一 线性表的顺序存储结构 实验学时 2学时 背景知识:顺序表的插入、删除及应用。 目的要求： 1掌握顺序存储结构的特点。 2掌握顺序存储结构的常见算法。 实验内容 1输入一组整型元素序列，建立顺序表。 2实现该顺序表的遍历。 3在该顺序表中进行顺序查找某一元素,查找成功返回1,否则返回0。 4判断该顺序表中元素是否对称,对称返回1,否则返回0。 5实现把该表中所有奇数排在偶数之前,即表的前面为奇数,后面为偶数。 6输入整型元素序列利用有序表插入算法建立一个有序表。 7利用算法6建立两个非递减有序表并把它们合并成一个非递减有序表。 8. 利用该顺序结构实现循环队列的入队、
2、出队操作。8编写一个主函数,调试上述算法。#include #include #define OVERFLOW 0#define MAXSIZE 100typedef int ElemType;typedef struct listElemType elemMAXSIZE;int length;Sqlist;void Creatlist(Sqlist printf(“请输入顺序表的长度：“); /输入一组整型元素序列，建立一个顺序表。scanf(“%d“,for(i=0;i=i;j-)L.elemj=L.elemj-1;L.elemj=x;L.length+;void Delete(Sqlis
3、t for(j=i;j=i;j-)L.elemj=L.elemj-1;L.elemi-1=x;L.length+;void Creatlist_sorted(Sqlist ElemType x;L.length=0;printf(“请输入顺序表的长度：“);scanf(“%d“,for(i=1;i=*b)c.elemk=*b;b+;k+;j+;else c.elemk=*a;a+;k+;i+;if(j=r.length)for(;kL.length+1)printf(“error!n“);break;printf(“请输入要插入的值 x:“);scanf(“%d“,Inseri(L,i,x);
4、printlist(L);break;case 5:printf(“请输入要删去的元素的位置 i:“);scanf(“%d“,if(iL.length)printf(“error!n“);break;Delete(L,i);printlist(L);break;case 6:Creatlist_sorted(L);printlist(L);break;case 7:Creatlist_sorted(L);Creatlist_sorted(M);Merger(L,M,N);printlist(N);break;case 8:Creatlist_sorted(L);printf(“请输入要插入的元
5、素 x:“);scanf(“%d“,Insert(L,x);printlist(L);break;实验二 链式存储结构（一）-单向链表的有关操作 实验学时 3学时 背景知识：单向链表的插入、删除及应用。 目的要求 1掌握单向链表的存储特点及其实现。 2掌握单向链表的插入、删除算法及其应用算法的程序实现。 实验内容 1随机产生或键盘输入一组元素，建立一个带头结点的单向链表（无序）。 2遍历单向链表。 3把单向链表中元素逆置（不允许申请新的结点空间）。 4在单向链表中删除所有的偶数元素结点。 5编写在非递减有序链表中插入一个元素使链表元素仍有序的函数，并利用该函数建立一个非递减有序单向链表。 6利
6、用算法5建立两个非递减有序单向链表，然后合并成一个非递增链表。 7利用算法5建立两个非递减有序单向链表，然后合并成一个非递减链表。 8利用算法1建立的链表，实现将其分解成两个链表，其中一个全部为奇数，另一个全部为偶数（尽量利用已知的存储空间）。* 9采用单向链表实现一元多项式的存储并实现两个多项式相加并输出结果。10在主函数中设计一个简单的菜单，分别调试上述算法。*11综合训练：利用链表实现一个班级学生信息管理（数据录入、插入、删除、排序、查找等，并能够实现将数据存储到文件中）/*单向链表的有关操作示例*/*类型定义及头文件部分,文件名为 sllink.h*/#include #include
7、 typedef int ElemType;/元素实际类型typedef struct LNodeElemType data;struct LNode *next;LNode,*LinkList; /定义结点、指针类型名/头插法建立无序链表void CreateList(LinkList ElemType e;L=(LinkList)malloc(sizeof(LNode);L-next=NULL;printf(“头插法建立链表，以 0 结束n“);scanf(“%d“,while(e)p=(LinkList)malloc(sizeof(LNode);p-data=e;p-next=L-nex
8、t;L-next=p;scanf(“%d“, /*非递减有序单向链表 L 插入元素 e 序列仍有序*/void Insert_Sort(LinkList s=(LinkList)malloc(sizeof(LNode);s-data=e;p=L;while(p-next/*查找插入位置*/s-next=p-next; /*插入语句*p 结点后插入*s 结点*/p-next=s;/*建立递增有序的单向链表*/void Create_Sort(LinkList L=(LinkList)malloc(sizeof(LNode);L-next=NULL;printf(“建立有序表，输入任意个整型数据以
9、 0 结束n“);scanf(“%d“,while(e)Insert_Sort(L,e);scanf(“%d“,/*单向链表的遍历*/void Traverse(LinkList L)LinkList p;printf(“遍历链表“);for(p=L-next;p;p=p-next)printf(“%5d“,p-data);printf(“n“);/*在单向链表删除元素 e*/void Delete(LinkList p=L;q=L-next;while(qq=q-next;if(!q) printf(“nnot deleted“);/*未找到元素 e*/else p-next=q-next;
10、/*找到删除*/free(q);/*单向链表的逆置*/void exch(LinkList p=L-next;L-next=NULL;while(p)s=p;p=p-next;s-next=L-next;L-next=s;/*两个非递减有序单向链表合并后仍为非递减序列*/void MergeIncrease(LinkList La,LinkList Lb,LinkList p=La-next;q=Lb-next;Lc=rear=La;free(Lb);while(pp=p-next; else s=q;q=q-next; rear-next=s;/*较小元素插入表尾*/rear=rear-ne
11、xt;if (p) rear-next=p; else rear-next=q实验三 迷宫问题求解实验学时 3学时 背景知识：栈的操作。 目的要求 1掌握栈的存储特点及其实现。 2掌握栈的出栈和入栈操作。实验内容：以一个 mxn 的长方阵表示迷宫，0 和 1 分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。要求：首先实现一个顺序或链表做存储结构的栈类型，然后编写一个求解迷宫的非递归程序。求得的通路以三元组(i, j, d)的形式输出，其中：(i, j)表示迷宫的坐标，d 表示走到下一坐标的方向。如对下面的迷宫，输出的一条通路为：（1
12、，1，1） ， （1，2，2） ， （2，2，2） ，（3，2，3） ， （3，1，2） ，.迷宫约定， x 方向为行方向，y 方向为列方向，迷宫开始坐标(左上角)为（ 1,1） 。#include #include #include struct nodeint sign;/标识 ,0 什么都不在 ,1 在 open 中,2 在 closed 中int flag;/标志位 0/1,0 可以走,1 不可以走int f,g,h;/判断函数int x,y;/坐标int old;/是否 old 节点,0 非,1 是;struct linknode fnode;link *next;link *pri
13、;link *open,*closed,*bestnode,*successor,*p,*q,*r,*s;int maze_flag77= 0,1,0,0,0,0,0,0,1,0,1,0,1,0,0,1,0,0,0,1,0,0,1,0,1,0,1,0,0,0,0,1,0,0,0,1,1,0,1,0,1,0,0,0,0,0,0,1,0;/表示迷宫的数组,0 可以走,1 不可以走node maze77;int judge(node n)/判断函数,判断 n 节点是否可以走if(n.flag=1)return(1);elsereturn(0);void in_open(node n)/将 n 节点放
14、入 open 表p=open;while(p-next!=open)if(n.f=p-fnode.f)p-next-pri=(link *)malloc(sizeof(link);p-next-pri-pri=p;p=p-next;p-pri-next=p;p-pri-pri-next=p-pri;p=p-pri;p-fnode.flag=n.flag;p-fnode.f=n.f;p-fnode.g=n.g;p-fnode.h=n.h;p-fnode.x=n.x;p-fnode.y=n.y;p-fnode.old=n.old;p-fnode.sign=n.sign=1;elsep=p-next;
