数据结构实验指导书(2016)(3)

void printlist_hc(struct sqlist *l) {int i;

printf(\当前表中信息如下:\\n\for(i=0;i<=l->length;i++)

{printf(\

实验三单链表的基本操作

实验预备知识：

1．熟练运用指针进行程序设计，掌握结构体指针。 2．掌握使用结构体指针访问结构体变量。 3．掌握指针作为函数的参数使用。

4．理解单链表的含义、目的和处理方法。

一、实验目的

1．掌握线性表的链式存贮结构及基本操作，深入了解链表的基本特性，以便在实际问题背景下灵活运用它们。

2．巩固该存贮结构的构造方法，深入理解和灵活掌握链表的插入、删除等操作。

二、实验环境

⒈ 硬件：每个学生需配备计算机一台。操作系统：DOS或Windows； ⒉ 软件：DOS或Windows操作系统+Turbo C；

三、实验要求

1．定义一链表类型，并定义带有头结点的单链表。

2．将教材中链表的建立、初始化、插入、删除等函数实现。

3．链表能够存储10名学生的基本信息（包括姓名、学号和成绩）。 4．由主函数按照用户要求对各个链表操作访问。

5．每次操作之前要有明确的说明，操作后要输出操作结果。 6．分析顺序表链表的插入、删除、查找的时间和空间复杂度。

四、实验内容

1．在自己的U盘的“姓名+学号”文件夹中创建“实验3”文件夹，本次实验的所有程序和数据都要求存储到本文件夹中。

2．完成链表操作的如下函数：建立，初始化，增加，插入，删除。 //链表插入、删除、合并 #include \#include\#include\

#define LEN sizeof(struct lnode_hc)

第8页 /共58页

#define LEN1 sizeof(struct hc_stu)

struct hc_stu {char name[3]; char num[3]; int cj; };

struct lnode_hc

{struct hc_stu *data; struct lnode_hc *next; };

void main()

{struct lnode_hc *jll();

void cshl(struct lnode_hc *head); void crl(struct lnode_hc *head); void scl(struct lnode_hc *head);

void hbl(struct lnode_hc *h1,struct lnode_hc *h2,struct lnode_hc *h3); struct lnode_hc *h1,*h2,*h3; char f;int i, k=0;

printf(\请选择对链表的操作，操作菜单如下：\\n\for(i=0;i<80;i++)printf(\printf(\建立链表(C)\\n\printf(\初始化链表(N)\\n\printf(\链表中插入元素(I)\\n\printf(\链表中删除元素(D)\\n\printf(\合并链表(H)\\n\printf(\退出系统(E)\\n\for(i=0;i<80;i++)printf(\do

{printf(\输入大写字母按Enter确定:\flushall(); f=getchar(); if(f=='C')

{if(k==0)h1=jll(); else h2=jll(); k++;}

else if(f=='N')

{if(k==1)cshl(h1);else cshl(h2);} else if(f=='I')

{if(k==1)crl(h1);else crl(h2);} else if(f=='D')

{if(k==1)scl(h1);else scl(h2);}

第9页 /共58页

else if(f=='H') {h3=jll();

hbl(h1,h2,h3);} }while(f!='E'); }

struct lnode_hc *jll() {struct lnode_hc *head;

head=(struct lnode_hc*)malloc(LEN); if(!head)printf(\出错!\\n\head->next=NULL; return (head);}

void cshl(struct lnode_hc *head) {void printl(struct lnode_hc *head); char x[3],y[3];int z;

struct lnode_hc *p1=head,*p2; printf(\请输入信息以-1结束:\\n\scanf(\while(z!=-1)

{p2=(struct lnode_hc*)malloc(LEN); if(!p2)printf(\出错!\\n\

p2->data=(struct hc_stu*)malloc(LEN1); if(!p2->data)printf(\出错!\\n\strcpy(p2->data->name,x); strcpy(p2->data->num,y); p2->data->cj=z; p2->next=NULL; p1->next=p2; p1=p2;

scanf(\printl(head);}

void crl(struct lnode_hc *head) {void printl(struct lnode_hc *head); int j;

struct lnode_hc *p,*p1=head;

printf(\请输入要插入信息的位置:\scanf(\

while(j-->1)p1=p1->next;

p=(struct lnode_hc*)malloc(LEN); if(!p)printf(\出错!\\n\

p->data=(struct hc_stu*)malloc(LEN1); if(!p->data)printf(\出错!\\n\

第10页 /共58页

printf(\请输入要插入的信息:\\n\

scanf(\p->next=p1->next;p1->next=p; printl(head);}

void scl(struct lnode_hc *head) {void printl(struct lnode_hc *head); int j;

struct lnode_hc *p1=head,*p2=head->next; printf(\请输入要删除信息的位置:\scanf(\while(j>1) {p1=p1->next; p2=p2->next; j--;}

printf(\删除的信息为:%s,%s,%d\\n\p1->next=p2->next;free(p2); printl(head);}

void hbl(struct lnode_hc *h1,struct lnode_hc *h2,struct lnode_hc *h3) {struct lnode_hc *p1,*p2,*p3;

p1=h1->next;p2=h2->next;h3=p3=h1; while(p1&&p2)

{if(p1->data->cj>p2->data->cj)

{p3->next=p1;p3=p1;p1=p1->next;} else

{p3->next=p2;p3=p2;p2=p2->next;}} p3->next=p1?p1:p2;free(h2); printl(h3);}

void printl(struct lnode_hc *head) {struct lnode_hc *p=head->next; printf(\当前表中元素如下:\\n\while (p->next!=NULL)

{printf(\p=p->next;}

printf(\}

实验四栈的基本操作

实验预备知识：

1．熟练运用线性结构进行数据处理，熟练使用指针进行数据访问。 2．掌握递归程序设计思想。

第11页 /共58页

3．掌握堆栈和队列的应用背景与场合。 4．理解堆栈和队列的数据类型。

一、实验目的

1．掌握栈的抽象数据类型。

2．掌握实现栈的各种操作的算法。 3．理解栈与递归的关系。

二、实验环境

⒈ 硬件：每个学生需配备计算机一台。操作系统：DOS或Windows； ⒉ 软件：DOS或Windows操作系统+Turbo C；

三、实验要求

1．用Ｃ描述栈的每种操作在顺序栈或链栈上的实现。

2.将建栈、初始化栈、判断栈是否非空、求栈的长度、输出从栈顶到栈底的元素分别定义为5个子函数，通过主函数实现对上述子函数的调用。

3. 输入数据：数据域（data）设定为整型。

四、实验内容

1．在自己的U盘的“姓名+学号”文件夹中创建“实验4”文件夹，本次实验的所有程序和数据都要求存储到本文件夹中。

2．定义两个堆栈：数据栈和操作栈。 3．实现如下堆栈处理函数。

建栈、初始化栈、判断栈是否非空、求栈的长度、输出从栈顶到栈底的元素 #include \#include \#include \#include \

#define STACK_INIT_SIZE 1 #define STACKINCREMENT 1 #define ERROR 0

typedef struct {char *base; char *top; int stacksize; }hc_sqstack;

void main()

{hc_sqstack *initstack_hc(); void cshstack_hc(hc_sqstack *s);

第12页 /共58页