《数据结构线性表的操作与实现》由会员分享，可在线阅读，更多相关《数据结构线性表的操作与实现（6页珍藏版）》请在金锄头文库上搜索。
1、任课教师：数据结构与算法（2011-2012 学年第 1 学期）实验报告学号：姓名：班级：实验一 线性表的基本操作与实现一、实验目的：1 复习 C 语言中指针、结构体、子程序调用等基础知识。2 掌握线性表的基本结构和操作方法，主要包括：顺序表、链表、循环链表、栈、队列等的基本操作与实现方法，培养学生灵活使用数据结构解决实际问题的能力。二、实验要求：1 复习 C 语言中指针的用法，特别是结构体的指针的用法；2 理解线性表中各种数据结构的基本概念以及相关操作的实现方法；主要包括：顺序表、链表、循环链表、栈、队列等；3 掌握应用线性表解决实际问题的一般方法和步骤。三、实验内容：1 基本部分：顺序表、
2、链表、循环链表等基本操作的理解与实现。1） 在计算机上先输入一串正整数的序列。请编写一个程序，首先用顺序表存储该序列。然后执行删除操作，即先从顺序表中找出最小的结点，删除它。然后再在剩余的表中，找出最小的结点，再删除之。直至表空为止。2） 已知两个单链表 A 和 B 分别表示两个集合，其元素递增排列。请编写程序求集合 A 和 B 的交集 C = AB，要求单链表 C 按其元素递增排列，并利用原表（即表 A 和表 B）的结点空间存放表 C。3） 假设有二个栈共同使用一块顺序存储的空间，为简单起见可设为共同使用数组 int buffer200。它们的栈底分别设在数组的两端，而栈顶指针在进行插入操作
3、时，向中间方向移动。请给出进出栈的程序。4） 在一次舞会上，来了许多男士和女士。这些男士和女士分别排队进入舞厅。第一个舞曲开始后，男士和女士按照队列顺序配对并走入舞池。当男士多于女士时，配对剩余的男士仍然在队列中。一曲终了，跳完舞的男士排在队尾，女士排成新的队列。下一舞曲开始时，男女重新按照队列顺序配对跳舞。当女士多于男士时，配对剩余的女士仍然在队列中，等待下一曲配对。现在要求按照队列中的先后顺序打印出第十轮配好对的人员名单和剩余人员的名单。2 综合部分：应用线性表解决实际问题。问题描述：从一个迷宫的入口到出口找出一条最短路经。用一个二维数组 MAZE(1：m，1：n)模拟迷宫，数组元素为 0
4、 表示该位置可以通过， 数组元素为 1 表示该位置不可以通行。MAZE(1，1) 和MAZE(m，n) 分别为迷宫的入口和出口。输入数据：a. 输入迷宫的大小 m 行和 n 列，两者为整数；b.由随机数产生 0 或 1，建立迷宫。输出数据：首先输出模拟迷宫的二维数组，若存在最短路经，则由出口回朔到入口打印这一条路径，如下所示：(m，n) ， ， (i，j)， ， (1，1)如无通道，则打印：There is no path.四、实验原理与算法设计：实现提示:(1) 数据结构1） 为了在程序中判断方便，把迷宫扩展成为 MAZE(0：m+1，0：n+1)，扩展部分的元素设置为 1，相当于在迷宫周围
5、布上一圈2） 不准通过的墙，这样，在迷宫的任一位置(i，j)上都有八个可以移动的方向。3） 用二维数组 MOVE(1：8，1：2)存放八个方向上的位置量，如图所示：MOVE 的设置情况如下表所示：ji 1 21 -1 02 -1 13 0 14 1 15 1 06 1 -17 0 -18 -1 -14） 为了标志已经通过的位置，采用一个标志数组 MARK（1.m，1.n）初值为 0，在寻找路径的过程中，若通过了位置（i，j） ，则将 MARK（i ，j）置为为 1。为了记录查找过程中到达位置及其前一位置，建立一个 Q（1.m*n-1， 0.2）数组，对于某一个数组元素 Q(P)，其中，Q(P，
6、0)和 Q(P，1)记下到达位置 i 和 j，Q(P，2) 记下其出发点在 Q 数组中的下标。算法基本思想将入口（1，1）作为第一个出发点，依次在八个反方向上搜索可通行的位置，形成第一层新的出发点，然后对第一层中各个位置分别搜索他所在八个方向上的可通行位置，形成第二层新的出发点，如此进行下去，直至达到出口(m，n)或者迷宫所有位置都搜索完毕为止。具体实施：从(m，n)开始，将其记入 Q 数组，比如记入 Q(1)，以它作为第一个出发点，依次对八个方向进行搜索，若下一个位置(i，j)可通行并且尚未经过（即 MAZE(I，j)=0 且 MARK(I，j)=0） ，则记入 Q 数组，如记在 Q(P)，
7、则在 Q(P，2)中要记下其出发点在 Q 数组中的下标 1，在八个方向上都搜索过以后，根据先进先出的原则 Q 从数组中重新取出一个位置作为新的出发点（这里，我们实际上把 Q 数组作为一个顺序表示的队列） ，重复以上过程，若能达到位置(m ，n) ，表示找到最短路径；若 Q 数组中已经没有位置可以作为新的出发点了，则表示迷宫没有通路。5）五、源程序代码：（含注释） 1.#include #define LIST_INIT_SIZE 100#define LISTNCREMENT 10typedef struct /*类型定义*/ElemType *elem;int length;int list
8、size;SqList;int main()int m,k=0,s;SqList *L; InitList_Sq (L) ;scanf(%d,&m);StatusListLength_Sq(SqList&L); Status ListDelete _Sq(SqList &L，int i，ElemType &e);while(A-length!=0) s=compare(L,k);deletenode(L,s);printf(The length is %2d:,L-length);printlist(L);Status InitList_Sq(SqList &L ) /*创建空的顺序表*/L.
9、elem=(ElemType*)malloc (LIST_SIZE_*sizeof(ElemType)If(!L.elem) exit(OVERFLOW);L.length=0;L.listsize=LIST_INIT_SIZE;return OK; /InitList_SqStatus ListLength _Sq(SqList &L) /赋值 int i,j=0,n;for(i=0;i+) scanf(%d,&n);while (n!=EOF)L.elemj=n;j+;L.length+=1; int compare (sqlist *L,int min)int i=0,j;for(j=i
10、+1;jlength;j+)if(L-datajdatai)min=j;return min;Status ListDelete _Sq(SqList &L) int i,min,k,h;for(k=0;k+)min=L.elemk;i=k;for(h=k+1;h+)if(L.elemhlength;j+) /删除程序L-dataj=L-dataj+1;L-length-;void printlist(sqlist *L) int i;for(i=0;ilength;i+)printf(%6d,L-datai);printf(n);2. #include #include #define MA
11、XSIZE 6SqList *InitList_Sq1(int n);SqList * InitList_Sq 2(int n);SqList * InitList_Sq 3(int n);typedef int ElemType;typedef struct node /类型定义ElemType data;struct node *next; SqList;main()slink *A,*B,*C;A= InitList_Sq 1(MAXSIZE);B= InitList_Sq 2(MAXSIZE);C= InitList_Sq 3(MAXSIZE);printf(the result is
12、:n);together(A,B,C);SqList *InitList_Sq1(int n) /创建一个含有的单链表SqList *A,*p,*s;int i;if(ndata);p-next=s;p=s; p-next=NULL;return(A);SqList * InitList_Sq 2(int n)slink *B,*m,*n;int i;if(ndata);m-next=n;m=n;m-next=NULL;return(B);SqList * InitList_Sq 3(int n)slink *C,*q,*k;int i;if(nnext=k;q=k;q-next=NULL;r
13、eturn(C);void hebing (SqList *A, SqList *B, SqList *C)int i=0;slink *m;slink *q;slink *p;m=A-next;q=B-next; /合并 2 个单链表p=C;while(m!=NULL) q=B-next;while(q!=NULL)if(m-data=q-data) /查找相同的点p-next=q;p=q;q=q-next;printf(%3d,p-data);break;q=q-next; m=m-next; /让指针指向下一个，继续查找printf(n);p-next=NULL;3.#include#d
14、efine INITSIZE 3typedef int ElemType;typedef structint top; /*类型定义*/ElemType *base;int stacksize;sqstack;void initstack(sqstack *s)s-base=(ElemType *)malloc(INITSIZE*sizeof(ElemType); /建一个空栈s-top=0;s-stacksize=INITSIZE;4.#include#include#define size 1200int m=-1,n=-1,j=0,k=0,l=0;typedef structlong s
15、tacksize; /类型定义int top;sequenstack;void initstack(sequenstack *s)s-top =-1; /创建一个空栈int stackempty(sequenstack *s)if(s-top =-1) /判断栈是否为空return 1; elsereturn 0;六、运行结果、测试分析与讨论：1. please enter the data：1234运行结果：the length is 3: 2 3 4the length is 2： 3 4the length is 1: 4the length is 0:2，please enter the data：1 2 3 4 5 please enter the data： 2 3 4 5 6运行结果：合并为 :2 3 4 51 复习 C 语言中指针的用法，特别是结构体的指针的用法；2.理解线性表中各种数据结构的
