2023年计算机本科数据结构与算法实验指导书.doc

实验一 线性表的实验一、实验目的1、掌握用Visual C+6.0上机调试顺序表的基本方法；2、掌握顺序表的基本操作，插入、删除、查找、以及有序顺序表的合并等算法的实现；3、掌握用Visual C+6.0上机调试单链表的基本方法；4、掌握单链表的插入、删除、查找、求表长以及有序单链表的合并算法的实现；5、进一步掌握循环单链表和双链表的插入、删除、查找算法的实现。二、实验内容下面是顺序表的部分基本操作实现的算法，请同学们自己设计主函数和部分算法，调用这些算法，完毕下面的实验任务。/*常用的符号常量定义*/# define OK 1# define ERROR 0# define MAXSIZE 10#define LIST_INIT_SIZE 10#define LISTINCREMENT 10 #define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define SUCCESS 1#define UNSUCCESS 0#define DUPLICATE -1#define NULLKEY 0 / 0为无记录标志#define N 10 / 数据元素个数#define EQ(a,b) (a)=(b)#define LT(a,b) (a)(b)#define LQ(a,b) (a)=(b)/* 定义ElemType为int或别的自定义类型 */typedef int ElemType; /* 顺序存储类型 */typedef struct int *elem;int length;int listsize;SqList; /*构造一个空线性表算法*/int InitList_Sq(SqList &L) /InitList_Sq() function /Inititial a Sq_ListL.elem=( ElemType *)malloc(LIST_INIT_SIZE *sizeof(ElemType);if (!L.elem) return(0);L.length=0;L.listsize=LIST_INIT_SIZE;return(1);/end of InitList_Sq() function/* 从顺序表中查找与给定元素值相同的元素在顺序表中的位置 */int LocateElem_Sq(SqList L, ElemType e)/LocateElem_Sq() sub-function int i=1; int *p=L.elem; while(i=L.length&*p+!=e) +i; if(i=L.length) return (i); else return (ERROR); /LocateElem_Sq() end /* 向顺序表中插入元素 */int ListInsert_sq(SqList &L,int i,int e)/ListInsert_sq() if(iL.length+1)/i (location) is illegal printf(Initial failure!n); return (ERROR); if(L.length=L.listsize) /insert into the end of the Sqlist ElemType *Newbase; Newbase=( ElemType *)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType); if(!Newbase) printf(Overflow!n); return (ERROR); L.elem=Newbase; L.listsize+=LISTINCREMENT; int *p,*q; q=&(L.elemi-1);/q point at the element before the inserted one for(p=&(L.elemL.length-1);p=q;-p) /move the element *(p+1)=*p; *q=e; +L.length; return (OK); /ListInser_sq() end/* 从顺序表中删除元素 */void ListDelete_Sq(SqList &L,int i, int &e) /ListDelete_Sq() function int *p,*q; if(iL.length) printf(“%d is OverFlow !n, i); exit(0); p=&(L.elemi-1); e=*p; q=L.elem+L.length-1; for (+p;p=q;+p) *(p-1)=*p; -L.length; printf(Success to Delete Sq_list !n);/end of ListDelete_Sq() function/* 有序顺序表的合并 */int Merge_Sq(SqList &A,SqList &B,SqList &C) /Merge_Sq() function /Merge the SqList A and B to C C.listsize=C.length=A.length+B.length; C.elem=(ElemType *)malloc(C.listsize*sizeof(ElemType); if(!C.elem) printf( OverFlow !n); /failure to allocate room in RAM return(0); ; int i=0,j=0; /i and j is the Subscript of A.elem and B.elem int k=0; /k is the Subscript of C.elem while(iA.length)&(jB.length ) /To merge when i =B.length if(A.elem i=B.elem j) C.elem k=A.elem i; i+;k+;/end of if else C.elem k=B.elem j; j+;k+;/end of else while(iA.length ) /insert the rest of SqList A C.elem k=A.elem i; i+;k+;/end of while while (jnext; while(p&jnext;+j; if(!p|ji) printf(The NO. %d element does not exist !n,i); exit(0); /end of if e=p-data; return (e); /end of GetElem_L() function/*单链表的插入元素*/int ListInsert_L(LinkList &L,int i,int e) /ListInsert_L() sub-function LNode *p=L; int j=0; while(p&jnext; +j; if(!p|ji-1)/out of location printf(Error! The location is illegal!n); return (ERROR); LNode *s; s=(Linklist)malloc(sizeof(LNode);/create new LNode s-data=e; s-next=p-next; p-next=s; return (OK); /ListInsert_L() end/*单链表的删除元素*/int ListDelete_L(LinkList &L,int i,int &e) /ListDelete_L() function /Delete the NO.i element of LinkList and return by variable e LNode *p,*q; int j=0; p=L; while(p-next&jnext;+j; if(!p|ji-1) printf(The NO. %d element does not exist !n,i); return(0); q=p-next; p-next=q-next; /delete the NO.i Node e=q-data; free(q); return (e); /end of ListDelete() function/*单链表的建立(头插法)*/void CreateList_L(LinkList &L,int n) /CreateList_L() function /To Creatre a LinkList L with HeadNode int i; LNode *p; L=(LinkList)malloc(sizeof(LNode); L-next=NULL; printf(Please input the data for LinkList Nodes: n); for(i=n;i0;-i) p=(LinkList)malloc(sizeof(LNode); scanf(“%d”,&p-data); /Reverse order inputing for Creating a LinkList p-next=L-next; L-next=p; /end of for if(n) printf(Success to Create a LinkList !n); else printf(A NULL LinkList have been created !n);/end of CreateList() function 1、顺序表基本操作的实现。规定生成顺序表时，可以键盘上读取元素，用顺序存储结构实现存储。2、已知顺序表la和lb中的数据元素按非递减有序排列，将la和lb表中的数据元素，合并成为一个新的顺序表lc，lc中的数据元素仍按非递减有序排列，并且不破坏la和lb表。3.从有序顺序表A中删除那些在顺序表B和顺序表C中都出现的元素.4、将一顺序存储的线性表（设元素均为整型量）中所有零元素向表尾集中，其他元素则顺序向表头方向集中。若输入：1 2 3 0 0 5 0 4 7 8则输出：1 2 3 5 4 7 8 0 0 05、单链表基本操作的实现。规定生成单链表时，可以键盘上读取元素，用链式存储结构实现存储。6、已知单链表la和lb中的数据元素按非递减有序排列，将la和lb中的数据元素,合并为一个新的单链表lc,lc中的数据元素仍按非递减有序排列。规定不破坏la表和lb表的结构。破坏la表和lb表的结构。7、编程实现两个循环单链表的合并。8、线性表的逆置：设有一个线性表（e0, e1, , en-2, en-1），请编写一个函数将这个线性表原地逆置，即将线性表内容置换为（en-1, en-2, , e1, e0）。线性表中的数据可认为整数、字符或字符串，试分别采用顺序存储结构和链式结构来实现。9、约瑟夫环的实现：设有n个人围坐一圈，用整数序列1, 2, 3, , n表达顺序围坐在圆桌周边的人， 现从某个位置 s上的人开始报数，数到m的人出列，接着从出列的下一个人又从1开始重新报数，数到m的人出列，如此下去，直到所有人都出列为此。试设计拟定他们的出列顺序序列的程序。如 n=8, m=4 ,s=1时， 设每个人的编号依次为 1，2，3，开始报数，则得到的出列顺序为4，8，5，2，1，3，7，6。检查程序的对的性和健壮性。(1)采用数组表达作为求解过程中使用的数据结构。(2) 采用单向循环链表作为存储结构模拟整个过程，循环链表可不设头节点,必须注意空表和非空表的界线。