2010级数据结构验证性实验指导书（新版）

数据结构验证性实验指导书

实验一 线性表的顺序存储实验

一、实验目的

1、掌握用Visual C++6.0上机调试顺序表的基本方法

2、掌握顺序表的基本操作，插入、删除、查找、以及有序顺序表的合并等算法的实现 二、实验内容

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

/*常用的符号常量定义*/ # 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=(int *)malloc(LIST_INIT_SIZE *sizeof(int)); if (!L.elem) return(0); L.length=0; L.listsize=LIST_INIT_SIZE; return(1);

- - 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 { cout <<\ getch();

return (ERROR); }

if(L.length>=L.listsize) //insert into the end of the Sqlist { int *Newbase;

Newbase=(int *)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(int)); if(!Newbase)

{ cout<<\ getch(); 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))

{ cout<

- - 2

数据结构验证性实验指导书

}

p=&(L.elem[i-1]); e=*p;

q=L.elem+L.length-1; for (++p;p<=q;++p) *(p-1)=*p; --L.length;

cout<<\}//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) { cout<<\ 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=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

while (j

cout<<\ return(1);

}//end of Merge_Sq() function

1、顺序表基本操作的实现。要求生成顺序表时，可以键盘上读取元素，用顺序存储结构实现存储。

2、已知顺序表la和lb中的数据元素按非递减有序排列，将la和lb表中的数据元素，合并成为一个新的顺序表lc，lc中的数据元素仍按非递减有序排列，并且不破坏la和lb

- -

3

数据结构验证性实验指导书

表。

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

实验二 单链表实验

一、实验目的

1、掌握用Visual C++6.0上机调试单链表的基本方法

2、掌握单链表的插入、删除、查找、求表长以及有序单链表的合并算法的实现 3、进一步掌握循环单链表的插入、删除、查找算法的实现

二、实现内容

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

/* 定义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 \ LNode *p; int j=1; p=L->next; while(p&&jnext;++j;} if(!p||j>i)

{ cout<<\ getch(); exit(0); }//end of if e=p->data; return (e);

}//end of GetElem_L() function

/*单链表的插入元素*/

- -

4

数据结构验证性实验指导书

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||j>i-1) //out of location

{ cout<<\ 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||j>i-1)

{ cout<<\ getch(); 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;

cout<<\ for(i=n;i>0;--i) {

- - 5

本文来源：https://www.bwwdw.com/article/r86v.html