《2022年计算机本科数据结构与算法实验指导书77 .pdf》由会员分享，可在线阅读，更多相关《2022年计算机本科数据结构与算法实验指导书77 .pdf（6页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、1 / 6 实验一线性表的实验一、实验目的1、掌握用 Visual C+6.0上机调试顺序表的基本方法；2、掌握顺序表的基本操作，插入、删除、查找、以及有序顺序表的合并等算法的实现；3、掌握用 Visual C+6.0上机调试单链表的基本方法；4、掌握单链表的插入、删除、查找、求表长以及有序单链表的合并算法的实现；5、进一步掌握循环单链表和双链表的插入、删除、查找算法的实现。二、实验内容下面是顺序表的部分基本操作实现的算法，请同学们自己设计主函数和部分算法，调用这些算法，完成下面的实验任务。/* 常用的符号常量定义*/ # define OK 1 # define ERROR 0 # defi
2、ne 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)=(
3、b) /* 定义 ElemType为int 或别的自定义类型 */ typedef int ElemType。/* 顺序存储类型 */ typedef struct int *elem。int length。int listsize。SqList。/* 构造一个空线性表算法*/ int InitList_Sq(SqList &L) /InitList_Sq() function 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 1 页，共 6 页2 / 6 /Inititial a Sq_List L.elem=(ElemType *)malloc(
4、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.leng
5、th) 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
6、=(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
7、。 *q=e。 +L.length。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 2 页，共 6 页3 / 6 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.lengt
8、h-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*s
9、izeof(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+。
10、/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。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 3 页，共 6 页4 / 6 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)
11、。 /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 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 4 页，共 6 页5 / 6 LNode *p=L。 int j=0。 while(p&jnext。 +j。 if(!p|ji-1) /out of location printf(Error! The loc
12、ation 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 v
13、ariable 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) /Cre
14、ateList_L() function /To Creatre a LinkList L with HeadNode int i。 LNode *p。 L=(LinkList)malloc(sizeof(LNode)。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 5 页，共 6 页6 / 6 L-next=NULL 。printf(Please input the data for LinkList Nodes: n)。 for(i=n。i0 。-i) p=(LinkList)malloc(sizeof(LNode)。scanf( “ %d ”
15、 ,&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 中的数据元素按非递减有序排列，将l
16、a 和 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 0 5、单链表基本操作的实现。要求生成单链表时，可以键盘上读取元素，用链式存储结构实现存储。6、已知单链表la 和 lb 中的数据元素按非递减有序排列，将la 和 lb 中的数据元素 ,合并为一个新的单链表l
17、c,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) 采用单向循环链表作为存储结构模拟整个过程，循环链表可不设头节点,必须注意空表和非空表的界限。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 6 页，共 6 页