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_List
L.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(i<1||i>L.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.elem[i-1]); //q point at the element before the inserted one
for(p=&(L.elem[L.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((i<1)||(i>L.length))
{ printf(“%d is OverFlow !\n", i);
exit(0);
}
p=&(L.elem[i-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((i<A.length)&&(j<B.length )) //To merge when i <=A.length and j>=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(i<A.length ) //insert the rest of SqList A
{ C.elem [k]=A.elem [i];
i++;k++;
}//end of while

while (j<B.length ) //insert the rest of SqList B
{ C.elem [k]=B.elem [j];
j++;k++;
}
printf("Success to Merge A and B !\n");
return(1);
}//end of Merge_Sq() function

下面是链表的部分基本操作实现的算法，请同学们自己设计主函数和部分算法，调用这些算法，完毕下面的实验任务。

/* 定义ElemType为int或别的自定义类型 */
typedef int ElemType;

/* 链式存储类型 */
typedef struct LNode
{ ElemType data;
struct LNode *next;
}LNode,*LinkList;

/* 单链表的取元素*/
int GetElem_L(LinkList L,int i,int &e) //GetElem_L() function
{//L is the HeadPointer of LinkList with HeadNode,when the No.i exist,assign the
//value to variable e and return "OK!" otherwise return "Error!"
LNode *p;
int j=1;
p=L->next;
while(p&&j<i)
{p=p->next;++j;}
if(!p||j>i)
{ 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&&j<i-1) //find the location
{ p=p->next;
++j;
}
if(!p||j>i-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&&j<i-1)
{ p=p->next;++j;
}
if(!p||j>i-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;i>0;--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 0
5、单链表基本操作的实现。规定生成单链表时，可以键盘上读取元素，用链式存储结构实现存储。
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) 采用单向循环链表作为存储结构模拟整个过程，循环链表可不设头节点,必须注意空表和非空表的界线。