《数据结构》基本操作指导参考模板范本.doc

1、目 录指导一、单链表的操作 - 2指导二、栈及其应用 - 10指导三、串的基本操作 - 16指导四、二叉树的基本操作 - 21指导五、图的存储和遍历 - 31指导六、查 找 - 41指导七、排 序 - 49指导一、单链表的操作一、指导目的1、掌握线性表的链式存储结构。2、掌握利用链式存储结构实现线性表的基本操作。3、掌握链式存储结构中的算法实现。二、指导内容1、建立带头结点的单链表，并输出该单链表。2、实现带头结点的单链表上的插入、删除、查找、修改操作。三、操作指导1、定义单链表的结点结构单链表的结点结构可为一个结构体类型(slnodetype)，其成员是数据域和指针域，数据域可以是整数。2、

2、模块划分和程序控制流程根据实验要完成的各功能，设置初始化、建立单链表、输出单链表、插入、删除、查找、修改和主函数8个模块，对于要完成的各功能，采用适当的人机界面，用循环和分支结构构成菜单进行选择。3、初始化模块int initiate(slnodetype *h)该模块中产生一个只有头结点的空单链表，用指针h作为函数的参数返回，因为h是指针变参，所以在函数的参数位置要以二级指针出现。在函数里，申请一个头结点空间。4、建立单链表模块int createlink(slnodetype *h)该模块中建立有若干个结点的单链表，用循环控制输入若干个整数，申请相应的结点空间，以输入的整数作为结点中的数据

3、，依次链接到初始只有头结点的单链表h中，可以把输入0作为建立链表的结束。5、输出单链表模块void display(slnodetype *h)对于传入的单链表h，依次输出单链表中的结点(数据)。 6、插入结点模块int inserti(slnodetype *h)设在第i个结点前插入数据为data的结点。在该函数模块中输入i和数据data，对于传入的单链表h，先查找是否存在插入的位置(单链表h中至少要有i-1个结点)，若不存在插入位置，则不做任何操作；若存在插入位置，则申请一个结点，其数据为data，挂在第i-1个结点的后面。7、删除结点模块int delete(slnodetype *h)

4、在该函数模块中，首先可以调用输出模块输出传入的单链表h，以便选择要删除的结点，然后输入要删除结点的数据data，再查找是否存在要删除的结点，若不存在要删除的结点，则显示相应的信息；若存在要删除的结点，则删除该结点(包括删除该结点空间)。8、查找模块int search(slnodetype *h)在该函数模块中，首先可以调用输出模块输出传入的单链表h，以便选择要查找的结点，然后输入要查找结点的数据data，再查找该结点是否存在，若不存在要查找的结点，则显示相应的信息；若存在要查找的结点，也显示相应的信息。 9、修改模块int modify(slnodetype *h)在该函数模块中，首先可以调

5、用输出模块输出传入的单链表h，以便选择要修改的结点，然后输入要修改结点的数据data，再查找该结点是否存在，若不存在要查找的结点，则显示相应的信息；若存在要查找的结点，则显示原结点的数据，再提示输入新的数据，输入新的数据后，可以再调用输出模块输出修改结点数据后的单链表h，以便查看修改后的单链表h中的数据。10、主函数main()主函数中定义指向单链表的指针等变量，首先调用初始化操作initiate( )，考虑人机界面，进入如下操作菜单的循环控制结构： = menu = 1- create 2- display 3- insert 4- delete 5- search 6- modify 0-

6、 exit choose the number between 0 to 6:对于要进行的操作，进入接受选择的循环控制(对于不合法的选择，重新提示选择)，对与合法的选择，退出接受选择的循环控制，进入多分支结构，以执行相应的功能，执行完毕后回到操作菜单的循环控制中，依然显示菜单，提示选择。当输入0(选择exit)，则程序实行结束。四、算法实现#include stdio.h#include alloc.h#include stdlib.htypedef struct slnodeint data; struct slnode *next;slnodetype;int initiate(slnod

7、etype *h)if(*h=(slnodetype *)malloc(sizeof(slnodetype)=NULL) return 0; (*h)-next=NULL; return 1;int createlink(slnodetype *h)int i=1,data;slnodetype *p,*s; printf(n create link n); p=h; printf( NO: %d: ,i); scanf(%d,&data); while(data!=0) s=(slnodetype *)malloc(sizeof(slnodetype); s-data=data;s-next

8、=NULL; p-next=s;p=s; printf( NO: %d: ,+i); scanf(%d,&data); void display(slnodetype *h)slnodetype *p; printf(n linklist:n); p=h-next; while(p) printf(%5d,p-data); p=p-next; int inserti(slnodetype *h)slnodetype *s,*p;int i,data,j=0; printf(n input i: );scanf(%d,&i); printf( input data: );scanf(%d,&da

9、ta); p=h; while(p!=NULL&jnext; j+; if(p!=NULL) s=(slnodetype *)malloc(sizeof(slnodetype); s-data=data; s-next=p-next; p-next=s; int delete(slnodetype *h)slnodetype *p,*q; int data; display(h); printf(n input data: );scanf(%d,&data); q=h;p=h-next; while(p!=NULL&p-data!=data) q=p; p=p-next; if(p=NULL)

10、 printf(n data %d nod found!,data); else q-next=p-next; free(p); int search(slnodetype *h)slnodetype *p,*q; int data; display(h); printf(n input data: );scanf(%d,&data); q=h;p=h-next; while(p!=NULL&p-data!=data) q=p; p=p-next; if(p=NULL) printf(n data %d nod found!,data); else printf(n data find!);i

11、nt modify(slnodetype *h)slnodetype *p,*q; int data; display(h); printf(n input data: );scanf(%d,&data); q=h;p=h-next; while(p!=NULL&p-data!=data) q=p; p=p-next; if(p=NULL) printf(n data %d nod found!,data); else printf(n old data: %d,p-data); printf(n new data: ); scanf(%d,&(p-data); display(h); mai

12、n()slnodetype *la;char ch; initiate(&la);clrscr(); ch=10; while(ch!=48) clrscr(); textcolor(13);gotoxy(28,3);cprintf(=); textcolor(14);gotoxy(38,3);cprintf( menu ); textcolor(13);gotoxy(44,3);cprintf(=); textcolor(12);gotoxy(24,5);cprintf(1-); textcolor(10);gotoxy(29,5);cprintf(create); textcolor(12

13、);gotoxy(46,5);cprintf(2-); textcolor(10);gotoxy(51,5);cprintf(display); textcolor(12);gotoxy(24,7);cprintf(3-); textcolor(10);gotoxy(29,7);cprintf(insert); textcolor(12);gotoxy(46,7);cprintf(4-); textcolor(10);gotoxy(51,7);cprintf(delete); textcolor(12);gotoxy(24,9);cprintf(5-); textcolor(10);gotox

14、y(29,9);cprintf(search); textcolor(12);gotoxy(46,9);cprintf(6-); textcolor(10);gotoxy(51,9);cprintf(modify); textcolor(12);gotoxy(36,11);cprintf(0-); textcolor(10);gotoxy(41,11);cprintf(exit); ch=10; while(ch64) textcolor(11);gotoxy(16,13);cprintf(choose the number between 0 to 6: ); textcolor(14);c

15、h=getche(); switch(ch) case 1: createlink(la);break; case 2: display(la);break; case 3: inserti(la);break; case 4: delete(la);break; case 5: search(la);break; case 6: modify(la);break; getch(); 五、运行和测试结果 = menu = 1- create 2- display 3- insert 4- delete 5- search 6- modify 0- exit choose the number

16、between 0 to 6: 1 create link NO: 1: 15 NO: 2: 23 NO: 3: 46 NO: 4: 8 NO: 5: 76 NO: 6: 59 NO: 7: 61 NO: 8: 2 NO: 9: 30 NO: 10: 0= menu = 1- create 2- display 3- insert 4- delete 5- search 6- modify 0- exit choose the number between 0 to 6: 2 linklist: 15 23 46 8 76 59 61 2 30= menu = 1- create 2- dis

17、play 3- insert 4- delete 5- search 6- modify 0- exit choose the number between 0 to 6: 3 input i: 5 input data: 28= menu = 1- create 2- display 3- insert 4- delete 5- search 6- modify 0- exit choose the number between 0 to 6: 2 linklist: 15 23 46 8 28 76 59 61 2 30= menu = 1- create 2- display 3- in

18、sert 4- delete 5- search 6- modify 0- exit choose the number between 0 to 6: 4 linklist: 15 23 46 8 28 76 59 61 2 30 input data: 100 data 100 not found!= menu = 1- create 2- display 3- insert 4- delete 5- search 6- modify 0- exit choose the number between 0 to 6: 4 linklist: 15 23 46 8 28 76 59 61 2

19、 30 input data: 76= menu = 1- create 2- display 3- insert 4- delete 5- search 6- modify 0- exit choose the number between 0 to 6: 2 linklist: 15 23 46 8 28 59 61 2 30= menu = 1- create 2- display 3- insert 4- delete 5- search 6- modify 0- exit choose the number between 0 to 6: 5 linklist: 15 23 46 8

20、 28 59 61 2 30 input data: 59 data find!= menu = 1- create 2- display 3- insert 4- delete 5- search 6- modify 0- exit choose the number between 0 to 6: 6 linklist: 15 23 46 8 28 59 61 2 30 input data: 46 old data: 46 new data: 89 linklist: 15 23 89 8 28 59 61 2 30= menu = 1- create 2- display 3- ins

21、ert 4- delete 5- search 6- modify 0- exit choose the number between 0 to 6: 0指导二、栈及其应用一、指导目的1、掌握栈的数据类型描述及栈的特点。2、掌握栈的顺序和链式两种存储结构的特点及算法描述。3、掌握栈的基本运算及算法在两种不同存储结构上的实现。二、指导内容1、设车辆厂生产了硬座车厢和软座车厢共n节(混合在一起)停放在一条列车轨道上，要求用顺序栈的操作使所有的硬座车厢排列到所有软座车厢的前面。2、将一个正整数n转换成十六进制数，要求用链栈的操作来实现。三、操作指导1、定义结构可以用宏定义定义车厢数的最大值。顺序栈结

22、构可为一个结构体类型(sqstack)，其成员是字符类型的栈空间数组和栈顶指针域(下标)。2、模块划分和程序控制流程根据实验要完成的各功能，设置栈初始化、栈满判断、栈空判断、入栈、出栈，输出列车和主函数7个模块，在主函数中首先产生由硬座车厢(可用H表示)和软座车厢(可用S表示)混合组成的列车，然后用栈操作实现实验的要求。3、初始化模块int initstack(sqstack *s)设置栈顶指针(下标)的初始值。进行初始化后的指针发生了变化，所以s是指针变量，以便函数模块外面使用的是变化了的值。4、栈满判断模块int full(sqstack *s)若栈满，则返回1。 5、栈空判断模块int

23、empty(sqstack *s)若栈空，则返回1。 6、入栈模块int push(sqstack *s,char x)若栈不满，对于要入栈的元素x，入栈到放车厢的栈s。7、出栈模块int pop(sqstack *s,char *x)若栈不空，进行出栈操作，出栈的元素由x返回，所以x是指针变量。 8、输出列车模块void display(char train,int n) 对于有n节车厢的列车(存放于train)，输出每节车厢(用H或S表示)。 9、主函数main()定义存放列车车厢的空间train和分别存放两种车厢的栈s1,s2等; 对两个栈进行初始化操作； 输入车厢数n； 初始化随机数种

24、子(randomize();/* 只要调用一次即可 */ 用随机数产生n节硬座车厢和软座车厢(产生0M-1的随机数函数为random(M); 输出产生的车厢； 对n节车厢，若是节硬座车，则进s1栈，否则进s2栈；把s1栈内的车厢依次倒入到列车轨道train中;把s2栈内的车厢依次接到列车轨道train中;输出列车轨道train中的车厢；四、第1题算法实现#includestdio.h#includeconio.h#includestdlib.h#define MAXNUM 50typedef structchar stackMAXNUM; int top;sqstack;int initsta

25、ck(sqstack *s)s-top=-1; return 1;int full(sqstack *s)if(s-top=MAXNUM-1) return 1; return 0;int empty(sqstack *s)if(s-toptop+; s-stacks-top=x; return 1;int pop(sqstack *s,char *x)if(empty(s) return -1; *x=s-stacks-top; s-top-; return 1;int gettop(sqstack *s,char *x)if(empty(s) return -1; *x=s-stacks-

26、top; return 1;void setempty(sqstack *s)s-top=-1;void display(char train,int n)int i; printf(n train:n); for(i=0;i50) exit(0); for(i=0;in;i+) k=random(2); if(k) traini=S; else traini=H; display(train,n); for(i=0;idata=e; p-next=NULL; (*s)=p;int pop(linkstack *s, char *e)linkstack *p; p=(*s); if(p=NUL

27、L) return 0; *e=p-data; (*s)=(*s)-next; free(p); return 1;main()int n,m,k;char ch; linkstack *s; clrscr(); s=NULL; printf(n input n: );八、第2题运行和测试结果 input n: 234 10 16 16 234 A 16 14 E 0 (10): 234 = (16): EA input n: 256 10 16 16 256 0 16 16 0 16 1 1 0 (10): 256 = (16): 100 input n: 32767 10 16 16 32

28、767 F 16 2047 F 16 127 F 16 7 7 0 (10): 32767 = (16): 7FFF scanf(%d,&n); m=n; printf(n 10 16); while(n!=0) k=n%16; if(k9) ch=k+55; else ch=k+48; push(&s,ch); printf(n 16 %5d %c,n,ch); n=n/16; printf(n %5d,n); printf(n (10): %d = (16): ,m); while(s!=NULL) pop(&s,&ch); printf(%c,ch); printf(n); getch(

29、);指导三、串的基本操作一、指导目的1、掌握串的存储及其特点。2、掌握串的基本运算及其算法实现。二、指导内容编程实现两个字符串的连接、比较操作，编程实现字符串求子串的操作。三、操作指导1、串结构定义本实验建议采用静态存储结构。串的存储空间的大小可用宏定义进行定义。串结构可为一个结构体类型(stringtype)，其成员是字符类型的数组和整数类型的串长度数据域。2、模块划分和程序控制流程根据实验要完成的各功能，设置求串长度、串的连接、串的比较，求子串和主函数5个模块，对于要完成的各功能，在主函数中，定义两个字符串，采用适当的人机界面，在循环显示菜单下再用循环来控制选择的功能模块号，然后在多分支结

30、构来执行相应的功能。3、求串长度模块int mystrlen(char *str)在该模块中计算串中的字符个数，并返回该个数。 4、串连接模块int strcat(stringtype s1,stringtype s2)该模块中首先输入两个字符串(可以用gets函数)，求得该两个字符串的长度，对于存储空间允许的这两个串s1，s2，将s2中的各字符依次接到s1的尾部，最后别遗漏在s1的尾部加上串结束标志。5、串比较模块int strcmp(stringtype s1,stringtype s2)该模块中首先输入两个字符串，求得该两个字符串的长度，依次比较两个串中的对应字符，遇到s1中的字符比s2中的字符大，比较结束，显