双向循环链表的创建

第一篇：双向循环链表的创建

#include #include #define OVERFLOW-2 #define ERROR 0 #define OK 1 typedef int status;//双向循环链表的存储结构 typedef struct DuLNode {

int data;

int Length;

struct DuLNode *prior;

struct DuLNode *next;} DuLNode,*DuLinkList;//构建一个空的双向循环链表 int InitList(DuLNode **p){

*p=(DuLNode *)malloc(sizeof(DuLNode));if(*p){

(*p)->next=(*p)->prior=*p;

(*p)->Length=0;} else

exit(OVERFLOW);} //双向循环链表的创建

int Create(DuLinkList &L,int n){ //输入n个元素的值，建立带头结点的双线循环链表L DuLinkList p=L,q;

int i;for(i=1;i<=n;i++){

q=(DuLinkList)malloc(sizeof(DuLNode));/*申请一个结点*/

printf(“请输入第%d个元素的值:”,i);

scanf(“%d”,&q->data);

p->next =q;

q->prior=p;

q->next=L;

L->prior =q;

p=q;

L->Length ++;} } //结点的输出

int Display(DuLinkList L){

DuLinkList p;

printf(“双向循环链表中的结点的数据为:”);

for(p=L->next;p->next!=L;){

printf(“%d”,p->data);

printf(“ ”);

p=p->next;}

printf(“%dn”,p->data);} //主函数实现双向循环链表的创建

int main(){

DuLinkList L;int n,i;

InitList(&L);printf(“请输入创建循环结点的个数:”);scanf(“%d”,&n);Create(L,n);Display(L);printf(“双向循环链表中结点的个数为:%dn”,L->Length);

return 0;}

第二篇：单链表实验报告

《数据结构》实验报告二

分校：

学号：

日期：

班级：

姓名：

程序名： L2311.CPP

一、上机实验的问题和要求：

单链表的查找、插入与删除。设计算法，实现线性结构上的单链表的产生以及元素的查找、插入与删除。具体实现要求：

1.从键盘输入20个整数，产生带表头的单链表，并输入结点值。

2.从键盘输入1个整数，在单链表中查找该结点。若找到，则显示“找到了”；否则，则显示“找不到”。

3.从键盘输入2个整数，一个表示欲插入的位置i，另一个表示欲插入的数值x，将x插入在对应位置上，输出单链表所有结点值，观察输出结果。4.从键盘输入1个整数，表示欲删除结点的位置，输出单链表所有结点值，观察输出结果。5.将单链表中值重复的结点删除，使所得的结果表中个结点值均不相同，输出单链表所有结点值，观察输出结果。

6.删除其中所有数据值为偶数的结点，输出单链表所有结点值，观察输出结果。

7.把单链表变成带表头结点的循环链表，输出循环单链表所有结点值，观察输出结果。8.（★）将单链表分解成两个单链表A和B，使A链表中含有原链表中序号为奇数的元素，而B链表中含有原链表中序号为偶数的元素，且保持原来的相对顺序，分别输出单链表A和单链表B的所有结点值，观察输出结果。

二、程序设计的基本思想，原理和算法描述：

（包括程序的结构，数据结构，输入/输出设计，符号名说明等）

三、源程序及注释：

四、运行输出结果：

五、调试和运行程序过程中产生的问题及采取的措施：

六、对算法的程序的讨论、分析，改进设想，其它经验教训：

七、对实验方式、组织、设备、题目的意见和建议：

第三篇：斐波那契数列递归和迭代&循环链表队列初始化实验报告

第一次实验实验报告

班级：2009211307 姓名：吕博文 学号：09211297 分工情况：个人一组 完成日期：11月5日

斐波那契数列递归和迭代算法

一、问题描述

分别写出下列函数的递归算法和迭代算法，并求出n=10时的函数值。Fib(n)= n

当n=0或n=1 Fib(n-2)+ Fib(n-1)当n>=2

二、算法思想

用递归算法求解时，若输入的n的值为0或1，根据问题描述中Fib(n)的递归定义，算法直接返回n作为输出结果。当输入的n的值大于等于2时，根据Fib(n)的递归定义，算法将调用自身计算Fib(n-2)和Fib(n-1)的值，然后返回二者的和。

用迭代算法求解时，先初始化Fib(0)和Fib(1)的值，用两个变量curValue和preValue存储，curValue存储较大的数值，preValue存储较小的数值。若输入的n的值为0或1，算法直接返回n。若输入的n的值大于等于2，循环n-1次，每次循环将curValue和preValue的值相加存入curValue中，并用preValue存储原来curValue的值，为下一次循环做好准备。最终的curValue的值即为Fib(n)的值。

三、设计描述

先提示输入n的值，然后调用递归算法计算Fib(n)，输出，再调用迭代算法计算Fib(n)，输出。

递归算法

int ShowFib_1(int n){

if(n == 0 || n == 1)//初始条件 return n;

else//不符合初始条件时，用递推关系计算 return ShowFib_1(n-2)+ ShowFib_1(n-1);}

迭代算法

int ShowFib_2(int n){ preValue = 0;curValue = 1;//设定第一、第二项的值作为初始条件

if(n == 0 || n == 1)//第一、第二项可直接输出结果 return n;else

{

for(i = 2;i <= n;i++)//其余各项从前往后逐项相加

{ temp = curValue;curValue = curValue + preValue;preValue = temp;

} returncurValue;

} }

四、源程序

#include using namespace std;

int ShowFib_1(int n);//定义递归函数 int ShowFib_2(int n);//定义迭代函数

int main(){ int n;

cout<< “N=?:”;cin>> n;

//递归算法

cout<< “用递归算法计算” <

//迭代算法

cout<< “用迭代算法计算” <

//递归算法

int ShowFib_1(int n){

if(n == 0 || n == 1)//判定初始条件 return n;else//

return ShowFib_1(n-2)+ ShowFib_1(n-1);}

//迭代算法

int ShowFib_2(int n){ intpreValue = 0, curValue = 1;//设定第一、第二项的值 if(n == 0 || n == 1)// return n;else

{

for(int i = 2;i <= n;i++)//其余项从前往后逐项相加

{ int temp;temp = curValue;curValue = curValue + preValue;preValue = temp;

} returncurValue;

} }

五、测试结果

N=40时利用递归求算时计算机反应速度较慢

N=10时

六、心得体会

在N=40时，等待递归算法算出结果时间较长，可见递归算法计算斐波那契数列的效率不高。但使用迭代算法则想法，可见虽然迭代算法的思路稍难于递归算法，但时间复杂度与空间复杂度均优于递归算法。故更应推荐迭代算法。

另外，本题难度低，过程中没什么问题，故无太多感想。

第二题

一、问题描述

假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点而不设头指针，试编写相应的队列初始化、入队列、出队列和判断队列状态的算法。

利用上述算法完成下面的各操作，并在每一操作后输出队列状态。

1)下列元素逐一入队：5,7,3,8,55 状态：5个元素

2)3个元素出队

状态：２个元素

3)再２个元素出队

状态：队空

4)再１个元素出队

状态：队空（指示下溢）

二、算法思想

主函数中新建一个队列的对象，然后调用其成员函数进行队列的操作。将5,7,3,8,55 入队→5,7,3出队→8,55出队→在队列为空时出队 每次操作后均输出当前队列状态。

三、设计描述

class Queue{

//建立一个队列类 public: Queue(){}

~Queue();

intInit();

//初始化队列 int Insert(int);

//入队 int Delete(int&);

//出队 intQState();

//判断状态 private:

typedefstruct node { int data;struct node *next;}Node;Node *rear;};

四、源程序

#include using namespace std;

class Queue { public: Queue(){} ~Queue();

intInit();//初始化队列

int Insert(int);//入队

int Delete(int&);//出队

intQState();//判断状态

private: typedefstruct node

{

int data;

struct node *next;}Node;Node *rear;};

int Queue::Init()//初始化 { rear=new Node;if(rear){

rear->data=-1;

rear->next=rear;

return 1;} return 0;}

int Queue::Insert(intelem)//入队 { Node * newd=new Node;

newd->data=elem;newd->next=rear->next;rear->next=newd;rear=newd;return 1;}

int Queue::Delete(int&elem)//出队 { if(rear==rear->next)

return 0;

Node *p=rear->next->next;elem=p->data;rear->next->next=p->next;if(p==rear)//删最后一个

rear=rear->next;free(p);return 1;

}

int Queue::QState()//判定状态 {

int i=0;Node *q=rear->next;

cout<<“队列状态:”<

cout<next->data<<“ ”;

q=q->next;

i++;} if(0==i)

cout<<“空”<

else

cout<

Queue::~Queue()//删除，如有未释放空间 { int i;if(rear)

} {

} if(rear->next==rear)free(rear);else { while(rear->next!=rear)

Delete(i);free(rear);} //主函数 int main(){ Queue DQ;intele;DQ.Init();DQ.QState();

cout<<“依次将5,7,3,8,55入队”<

5,7,3,8,55

cout<<“将5,7,3出队n”;system(“pause”);

if(DQ.Delete(ele))// 出队

cout<

if(DQ.Delete(ele))

cout<

if(DQ.Delete(ele))

cout<

DQ.QState();//当前状态 8,55 cout<<“再将8,55出队”<

system(“pause”);

if(DQ.Delete(ele))

cout<

cout<

cout<<“下一步将在空的队列里进行删除操作”<

if(DQ.Delete(ele))

cout<

} cout<<“队列已满，下溢”<

system(“pause”);

五、测试结果

六、心得体会

这个程序的实现关键在于类，类对于数据结构可以说是非常重要非常基础也是必不可少的一个杀手锏。在编这道题的过程中，最初的想法是设计一个程序可以实现入队、出队、上溢下溢提示，但考虑到这道题的具体要求，改为了程序自动将题目所要求出入队的元素进行操作，不过不影响核心算法核心思想的实现。

第四篇：学生管理系统学生链表

#include #include #include

typedef struct student { int num;char name[10];char passwd[6];int age;int class;int math;int clan;int chinese;int mingci;struct student *next;}STU,*pstu;

pstu stu_numsort(pstu head);pstu stu_sumsort(pstu head);pstu stu_mathsort(pstu head);pstu stu_chisort(pstu head);pstu stu_clansort(pstu head);pstu stu_searchbynum(pstu head,int num);pstu stu_searchbyname(pstu head,char name[]);pstu stu_searchbyclass(pstu head,int class);pstu stu_create(){

pstu head=NULL;pstu s=NULL;int num;char name[10];char passwd[6];int age;int class;int math;int clan;int chinese;int mingci;printf(“请输入任意一个数非0的数继续 ：”);scanf(“%d”,&num);while(num!=0){

s=(pstu)malloc(sizeof(STU));

if(s==NULL)

{

printf(“nmalloc errorn”);

return NULL;

}

printf(“输入学生学号：”);

scanf(“%d”,&s->num);

printf(“请输入学生姓名：”);

scanf(“%s”,s->name);

printf(“请输入登陆密码：”);//学生权限（error）

scanf(“%s”,s->passwd);

printf(“请输入学生年龄：”);

scanf(“%d”,&s->age);

printf(“请输入学生班级：”);

scanf(“%d”,&s->class);

printf(“请输入数学成绩：”);

scanf(“%d”,&s->math);

printf(“请输入c语言成绩：”);

scanf(“%d”,&s->clan);

printf(“请输入语文成绩：”);

scanf(“%d”,&s->chinese);

printf(“enter next studentn”);

if(head==NULL)

{

s->next=NULL;

head=s;

}

else

{

s->next=NULL;

s->next=head;

head=s;

}

scanf(“%d”,&num);} return head;} //保存

void stu_write(pstu head){ int flag=0;FILE *fp=NULL;pstu p=head;fp=fopen(“num”,“w”);if(fp==NULL){

printf(“open errorn”);

return;} while(p!=NULL){

flag=fwrite(p,sizeof(STU),1,fp);

if(flag!=1)

{

printf(“write errorn”);

return;

}

p->next;} fclose(fp);} //读函数

pstu stu_read(){ FILE *fp=NULL;pstu head=NULL;pstu s=NULL;fp=fopen(“num”,“r”);s=(pstu)malloc(sizeof(STU));while(fread(s,sizeof(STU),1,fp)==1){

if(head==NULL)

{

s->next=NULL;

head=s;

}

else

{

s->next=NULL;

s->next=head;

head=s;

}

s=(pstu)malloc(sizeof(STU));} fclose(fp);return head;} //删除学生信息(学号)pstu stu_del(pstu head,int num){ pstu p=head;pstu q=NULL;printf(“输入删除的学号：”);scanf(“%d”,&num);if(head->num==num){

head=head->next;} else {

while(p->next!=NULL)

{

if(p->next->num==num)

{

q=p->next;

p->next=q->next;

free(q);

q=NULL;

break;

}

p=p->next;

} } return head;}

pstu stu_searchbynum();//按学号修改学生信息

void stu_changebynum(pstu head){ pstu p=head;int num;char name[10];char passwd[6];int age;int class;int math,chinese,clan;int n;printf(“请输入查找的学号：”);scanf(“%d”,&num);while(p!=NULL){

if(p->num==num)

{

printf(“学号t姓名t密码t年龄t班级t数学tc语言t语文t名次n”);

printf(“%dt%st%st%dt%dt%dt%dt%dt%dn”,p->num,p->name,p->passwd,p->age,p->class,p->math,p->clan,p->chinese,p->mingci);

break;

}

p=p->next;}

printf(“请选择需要修改的学生信息：n”);printf(“-------------------------n”);printf(“1：姓名n”);printf(“2：密码n”);printf(“3：年龄n”);printf(“4：班级n”);printf(“5：数学成绩n”);printf(“6：c成绩n”);printf(“7：语文成绩n”);printf(“0：退出”);printf(“---------------------------n”);printf(“请输入需要修改的信息：”);scanf(“%d”,&n);switch(n){

case 0:

return;

case 1:

printf(“请输入新的姓名：”);

scanf(“%s”,p->name);

break;

case 2:

printf(“请输入新的密码：”);

scanf(“%s”,p->passwd);

break;

case 3:

printf(“请输入新的年龄：”);

scanf(“%d”,&p->age);

break;

case 4:

printf(“请输入新的班级：”);

scanf(“%d”,&p->class);

break;

case 5:

printf(“请输入新的数学成绩：”);

scanf(“%d”,&p->math);

break;

case 6:

printf(“请输入新的c语言成绩：”);

scanf(“%d”,&p->clan);

break;

case 7:

printf(“请输入新的语文成绩：”);

scanf(“%d”,&p->chinese);

break;

default:

printf(“n无效选项n”);

break;} printf(“修改成功！n”);printf(“学号t姓名t密码t年龄t班级t数学tc语言t语文t名次n”);

printf(“%dt%st%st%dt%dt%dt%dt%dt%dn”,p->num,p->name,p->passwd,p->age,p->class,p->math,p->clan,p->chinese,p->mingci);} //按学生姓名修改

void stu_changebyname(pstu head){ pstu p=head;int num;char name[10];char passwd[6];int age;int class;int math,chinese,clan;int n;printf(“请输入查找的姓名：”);scanf(“%s”,name);while(p!=NULL){

if(strcmp(p->name,name)==0)

{

printf(“学号t姓名t密码t年龄t班级t数学tc语言t语文t名次n”);

printf(“%dt%st%st%dt%dt%dt%dt%dt%dn”,p->num,p->name,p->passwd,p->age,p->class,p->math,p->clan,p->chinese,p->mingci);

break;} p=p->next;} printf(“请选择需要修改的学生信息：n”);printf(“-------------------------n”);printf(“1：学号n”);printf(“2：密码n”);printf(“3：年龄n”);printf(“4：班级n”);printf(“5：数学成绩n”);printf(“6：c成绩n”);printf(“7：语文成绩n”);printf(“0：退出”);printf(“---------------------------n”);printf(“请输入需要修改的信息：”);scanf(“%d”,&n);switch(n){ case 0:

return;case 1:

printf(“请输入新的学号：”);

scanf(“%d”,&p->num);

break;case 2:

printf(“请输入新的密码：”);

scanf(“%s”,p->passwd);

break;case 3:

printf(“请输入新的年龄：”);

scanf(“%d”,&p->age);

break;case 4:

printf(“请输入新的班级：”);

scanf(“%d”,&p->class);

break;case 5:

printf(“请输入新的数学成绩：”);

scanf(“%d”,&p->math);

break;case 6:

printf(“请输入新的c语言成绩：”);

scanf(“%d”,&p->clan);

break;

case 7:

printf(“请输入新的语文成绩：”);

scanf(“%d”,&p->chinese);

break;

default:

printf(“n无效选项n”);

break;} printf(“修改成功！n”);printf(“学号t姓名t密码t年龄t班级t数学tc语言t语文t名次n”);

printf(“%dt%st%st%dt%dt%dt%dt%dt%dn”,p->num,p->name,p->passwd,p->age,p->class,p->math,p->clan,p->chinese,p->mingci);

} void change_printf(pstu head){ pstu p=head;int n;printf(“请选择修改学生信息的方式：n”);printf(“-------n”);printf(“1:按学生学号修改n”);printf(“2:按学生姓名修改n”);printf(“0:退出n”);printf(“---------n”);scanf(“%d”,&n);switch(n){

case 1:

stu_changebynum(head);

printf(“显示全部学生信息：”);

break;

case 2:

stu_changebyname(head);

printf(“显示全部学生信息：”);

break;

case 3:

return;} } //查找学生信息

void search_printf(pstu head){ pstu p=head;int n;int num;char name[10];int class;printf(“请选择查找学生信息的方式：n”);printf(“-------n”);printf(“1:按学生学号查找n”);printf(“2:按学生姓名查找n”);printf(“3:按班级群体查找n”);printf(“0:退出n”);printf(“---------n”);scanf(“%d”,&n);switch(n){

case 1:

stu_searchbynum(head,num);

break;

case 2:

stu_searchbyname(head,name);

break;

case 3:

stu_searchbyclass(head,class);

break;

case 0:

return;} } //1：学号查找

pstu stu_searchbynum(pstu head,int num){ pstu p=head;printf(“请输入查找的学号：”);scanf(“%d”,&num);while(p!=NULL){

if(p->num==num)

break;

p=p->next;} return p;} //2:按姓名查找 pstu stu_searchbyname(pstu head,char name[]){ pstu p=head;printf(“请输入要查找的姓名：”);scanf(“%s”,name);while(p!=NULL){

if(strcmp(name,p->name)==0)

break;

p=p->next;} return p;} //班级群体查找

pstu stu_searchbyclass(pstu head,int class){ pstu p=head;printf(“请输入要查找的班级：”);scanf(“%d”,&class);while(p!=NULL){

if(p->class==class)

break;

p=p->next;} return p;}

//显示所有学生信息列表

void sort_printf(pstu head){ pstu p=head;int n;printf(“请选择显示学生信息的方式：n”);printf(“-----n”);printf(“1：按学号顺序显示n”);printf(“2：按名次显示n”);printf(“3：按数学成绩显示n”);printf(“4：按c语言成绩显示n”);printf(“5：按语文成绩显示n”);printf(“--------n”);printf(“请输入你要选择的操作：”);scanf(“%d”,&n);switch(n){

case 1:

stu_numsort(head);

printf(“显示学生信息n”);

break;

case 2:

stu_sumsort(head);

printf(“显示学生信息n”);

break;

case 3:

stu_mathsort(head);

printf(“显示学生信息n”);

break;

case 4:

stu_clansort(head);

printf(“显示学生信息n”);

break;

case 5:

stu_chisort(head);

printf(“显示学生信息n”);

break;

case 6:

return;

default:

printf(“输入错误n”);

break;} }

int stu_len(pstu head){ pstu p=head;int len=0;while(p!=NULL){

len++;

p=p->next;} return len;} //1：按学号顺序显示

pstu getnummax(pstu head){ pstu pmax=head;if(head==NULL){

return NULL;} pstu p=head->next;while(p!=NULL){

if(pmax->num

num)

{

pmax=p;

}

p=p->next;} return pmax;} pstu removefromold(pstu head,pstu pmax){ pstu p=head;if(head==pmax){

head=head->next;} else {

while(p!=NULL)

{

if(p->next==pmax)

{

p->next=pmax->next;

break;

}

}

p=p->next;} return head;} pstu add(pstu pnew,pstu pmax){ pmax->next=pnew;pnew=pmax;return pnew;} pstu stu_numsort(pstu head){ pstu pold=head;pstu pmax=NULL;pstu pnew=NULL;while(pold!=NULL){

pmax=getnummax(pold);

pold=removefromold(pold,pmax);

pnew=add(pnew,pmax);} return pnew;} //按名次显示

pstu getsummin(pstu head){ pstu pmin=head;if(head==NULL){

return NULL;} pstu p=head->next;while(p!=NULL){

if(pmin->math+pmin->clan+pmin->chinese>p->math+p->clan+p->chinese)

{

pmin=p;

}

p=p->next;} return pmin;} pstu removefromtold(pstu head,pstu pmin){ pstu p=head;if(head==pmin){

head=head->next;} else {

while(p!=NULL)

{

if(p->next==pmin)

p->next=pmin->next;

break;

}

p=p->next;} return head;} pstu addt(pstu pnew,pstu pmin){ pmin->next=pnew;pnew=pmin;return pnew;} pstu stu_sumsort(pstu head){ pstu pold=head;pstu pmin=NULL;pstu pnew=NULL;int i=stu_len(head);while(pold!=NULL){

pmin=getsummin(pold);

pold=removefromtold(pold,pmin);

pnew=addt(pnew,pmin);

pnew->mingci=i--;} return pnew;} //按数学成绩显示

pstu getmathmin(pstu head){ pstu pmin=head;if(head==NULL){

return NULL;} pstu p=head->next;while(p!=NULL){

if(pmin->math>p->math)

{

pmin=p;

}

p=p->next;} return pmin;} pstu stu_mathsort(pstu head){ int i=stu_len(head);pstu pold=head;pstu pmin=NULL;pstu pnew=NULL;while(pold!=NULL){

pmin=getmathmin(pold);

pold=removefromold(pold,pmin);

pnew=add(pnew,pmin);

pnew->mingci=i--;} return pnew;} //按c语言成绩显示

pstu getclanmin(pstu head){ pstu pmin=head;if(head==NULL){

return NULL;} pstu p=head->next;while(p!=NULL){

if(pmin->clan>p->clan)

{

pmin=p;

}

p=p->next;} return pmin;} pstu stu_clansort(pstu head){ int i=stu_len(head);pstu pold=head;pstu pmin=NULL;pstu pnew=NULL;while(pold!=NULL){

pmin=getclanmin(pold);

pold=removefromtold(pold,pmin);

pnew=addt(pnew,pmin);

pnew->mingci=i--;} return pnew;} //按语文成绩显示

pstu getchimin(pstu head){ pstu pmin=head;if(head==NULL){

return NULL;} pstu p=head->next;while(p!=NULL){

if(pmin->chinese>p->chinese)

{

pmin=p;

}

p=p->next;} return pmin;} pstu stu_chisort(pstu head){ int i=stu_len(head);pstu pold=head;pstu pmin=NULL;pstu pnew=NULL;while(pold!=NULL){

pmin=getchimin(pold);

pold=removefromtold(pold,pmin);

pnew=addt(pnew,pmin);

pnew->mingci=i--;} return pnew;} void stu_printf(pstu head){ pstu tmp=head;printf(“学号t姓名t密码t年龄t班级t数学tc语言t语文t名次n”);while(tmp!=NULL){

printf(“%dt%st%st%dt%dt%dt%dt%dt%dn”,tmp->num,tmp->name,tmp->passwd,tmp->age,tmp->class,tmp->math,tmp->clan,tmp->chinese,tmp->mingci);

tmp=tmp->next;} printf(“n”);} void stun_printf(pstu head){ pstu tmp=head;printf(“学号t姓名t密码t年龄t班级t数学tc语言t语文t名次n”);while(tmp!=NULL){

printf(“%dt%st%st%dt%dt%dt%dt%dt%dn”,tmp->num,tmp->name,tmp->passwd,tmp->age,tmp->class,tmp->math,tmp->clan,tmp->chinese,tmp->mingci);

break;} printf(“n”);}

//2: int main(){ // int m;int num;int class;int len;char name[10];pstu head=stu_create();stu_printf(head);len=stu_len(head);// pstu p=stu_del(head, num);// stu_printf(p);/* pstu k=stu_searchbynum(head,num);if(k!=NULL)

stun_printf(k);else

printf(“no find”);

pstu l=stu_searchbyname(head,name);

// // // // // //

// // // // // //

} if(l!=NULL)stun_printf(l);else printf(“no find”);pstu h=stu_searchbyclass(head,class);if(h!=NULL)stun_printf(h);else printf(“no find”);*/ stu_changebynum(head);printf(“显示全部学生信息：”);stu_printf(head);stu_changebyname(head);printf(“显示全部学生信息：”);stu_printf(head);search_printf(head);stun_printf(head);change_printf(head);stu_printf(head);pstu p1=stu_numsort(head);stu_printf(p1);pstu p2=stu_sumsort(head);stu_printf(p2);pstu p3=stu_mathsort(head);stu_printf(p3);sort_printf(head);stu_printf(head);

第五篇：2012《数据结构》上机实验报告 链表

西华大学数计学院学生上机实践报告

西华数学与计算机学院上机实践报告

课程名称：数据结构 指导教师：唐剑梅 上机实践名称：

上机实践编号：1 年级： 2011 姓名：蒋俊 学

号

：

***

上机实践成绩：

上机实践日期：2012-11-6

上机实践时间：8:00-9:30

一、实验目的

1.了解线性表的逻辑结构特性，以及这种特性在计算机内的两种存储结构。

2.重点是线性表的基本操作在两种存储结构上的实现；其中以链表的操作为侧重点；并进一步学习程序设计方法。

3.掌握栈这种数据结构特性及其主要存储结构，并能在现实生活中灵活运用。

4.掌握队列这种数据结构特性及其主要存储结构，并能在现实生活中灵活运用。

5.了解和掌握递归程序设计的基本原理和方法。

6.掌握使用 C++面向对象的程序设计技术设计数据结构源程序的方法。

二、实验内容

1.熟悉前面的【程序示例2】，按照约瑟夫问题的方法2，试着不设头结点改写原来的程序，上机调试运行。

2.用链表建立通讯录。通讯录内容有：姓名、通讯地址、电话号码。

要求：（1）通讯录按姓名项的字母顺序排列；

（2）能查找通讯录中某人的信息；

[提示] 用链表来存放这个通讯录，一个人的信息作为一个结点。成链的过程可以这样考虑：先把头结点后面的

西华大学数计学院学生上机实践报告

char name[20];

// 姓名子域

NodeType *next;

// 指针域

};class Jose

//类声明

{ private: NodeType *Head;

public:

Jose(){};

~Jose(){ };

void creat();

void outs();

};void Jose::creat(){ int i=0, n;

NodeType *newp, *pre;

cout<<“n

输入总人数 n=”;cin>>n;

pre=new NodeType;

Head=new NodeType;

pre->num=1;

cout<<“n 编号”<<1<<“的人

姓名=”;

cin>>pre->name;

cout<<“n 密码”<<1<<“的人

密码=”;

cin>>pre->psw;

Head=pre;

Head->next=Head;

for(i=1;i

{ newp=new NodeType;

newp->num=i+1;

cout<<“n 编号”<

姓名=”;cin>>newp->name;

cout<<“n 密码”<

密码=”;

cin>>newp->psw;

newp->next=Head;

pre->next=newp;

pre=newp;

} }

void Jose::outs()

{ int m,i;

NodeType *q=Head, *p;

cout<<“n 输入m值(m>=2)”;cin>>m;

cout<<“n

根据m值，开始报数输出：”<

while(q->next!=q)

西华大学数计学院学生上机实践报告

{ for(i=1;inext;}

cout<<“编号为：”<num<<“ 的人的姓名：”<name<

cout<<“n 编号为:”<num<<“的人的密码：”<psw<

m=q->psw;

p->next=q->next;delete q;

q=p->next;

}

cout<<“编号为：”<num<<“的人的姓名：”<name<

cout<<“n 编号为:”<num<<“的人的密码：”<psw<

delete q;}

int main()

{

Jose h;

h.creat();

h.outs();

return 0;}

西华大学数计学院学生上机实践报告

{ char Add[20];

char name[20];

char tel[20];

};struct NodeType {

ElemType data;

NodeType *next;};class Sqlist

{ private:

NodeType *Head;

public:

Sqlist();

~Sqlist();

void creat();

void Insert(ElemType x);

void Delet(ElemType x);

void PrintOut();

};Sqlist::Sqlist(){

Head=new NodeType;Head->next=NULL;strcpy(Head->data.name,“姓名”);strcpy(Head->data.Add,“地址”);strcpy(Head->data.tel,“电话号码”);} Sqlist::~Sqlist(){

NodeType *p=Head->next;

while(p!=NULL)

{Head->next=p->next;

delete p;

p=Head->next;} } void Sqlist::creat()

//初步建立一个通讯录

{ NodeType*p,*s,*q;ElemType x;

西华大学数计学院学生上机实践报告

int a;q=Head;cout<<“n 输入姓名：”;cin>>x.name;cout<<“n 输入通讯地址：”;cin>>x.Add;cout<<“n 输入电话号码：”;cin>>x.tel;p=new NodeType;p->data=x;Head->next=p;p->next=NULL;cout<<“输入一个数。若为-1，结束输入:”<>a;

while(a!=-1){ cout<<“n 输入姓名：”;cin>>x.name;cout<<“n 输入通讯地址：”;cin>>x.Add;cout<<“n 输入电话号码：=”;cin>>x.tel;s=new NodeType;s->data=x;if(strcmp(s->data.name,p->data.name)>0){ p->next=s;s->next=NULL;

p=s;} else{ s->next=p;q->next=s;} q=q->next;

cout<<“输入一个数。若为-1，结束输入:”<>a;} } void Sqlist::Insert(ElemType x)//插入 { NodeType *p,*q,*s;s=new NodeType;

西华大学数计学院学生上机实践报告

s->data=x;q=Head;p=q->next;while(p!=NULL&&strcmp(p->data.name,x.name)<0){q=p;p=p->next;} s->next=p;q->next=s;} void Sqlist::Delet(ElemType x)//删除 { NodeType *p,*q;q=Head;p=Head->next;while(p!=NULL&&strcmp(p->data.name,x.name)!=0){q=p;p=p->next;} if(p!=NULL){ q->next=p->next;delete p;cout<<“删除结点成功”<

{ NodeType *p;p=Head->next;while(p!=NULL){ cout<

data.name<<“ ”;cout<

data.tel<<“ ”;cout<

data.Add<<“ ”;p=p->next;} cout<

Sqlist as;

cout<<“n

通讯录演示”;

do{

cout<<“nn”;

cout<<“nn

1.初步建立一个通讯录（单链表）

”;

西华大学数计学院学生上机实践报告

cout<<“nn

2.插入新的电话记录 ”;

cout<<“nn

3.删除一个电话记录”;

cout<<“nn

4.结束程序”;

cout<<“n******************************** ”;

cout<<“n

请输入你的选择(1,2,3,4)”;cin>>k;switch(k){ case 1:{ as.creat();as.PrintOut();}break;

case 2:{

cout<<“n 插入的数据 姓名”;cin>>e.name;

cout<<“n 插入的数据 电话号”;cin>>e.tel;

cout<<“n 插入的数据 地址”;cin>>e.Add;

as.Insert(e);as.PrintOut();

}break;

case 3:{

cout<<“n 被删除的姓名= ”;

cin>>e.name;

as.Delet(e);

as.PrintOut();

}break;

default:break;

}

}while(k>=1&&k<4);

cout<<“n

再见!”;

return 0;}

西华大学数计学院学生上机实践报告

西华大学数计学院学生上机实践报告

西华大学数计学院学生上机实践报告

const int MAXSIZE=100;

// 数组的容量 class SqStack

{ private:

ElemType elem[MAXSIZE];

int top;

public:

SqStack();

~SqStack(){};

void SqStack::push(ElemType e);

ElemType SqStack::pop();

void SqStack::PrintOut();

int SqStack::IsEmpty();

void f(ElemType N,ElemType M);};void SqStack::f(ElemType N,ElemType M){ SqStack s;

ElemType e;while(N){

s.push(N%M);

N=N/M;} while(!s.IsEmpty()){

e=s.pop();

if(e>=10)

{

e=e%10;

switch(e)

{

case 1:cout<<“b”<

case 2:cout<<“c”<

case 3:cout<<“d”<

case 4:cout<<“e”<

case 5:cout<<“f”<

default:cout<<“a”<

}

} else

cout<

西华大学数计学院学生上机实践报告

} cout<

{cout<<“栈满溢出”<

return;

}

else{top++;

elem[top]=e;} } ElemType SqStack::pop(){ElemType x;

if(top==0)

{ cout<< “ 栈为空，不能出栈操作”<

else { x=elem[top];

top--;

return x;} } void SqStack::PrintOut()

{int k;

cout<<“n PrintOut Data:n”;

for(k=top;k>=1;k--)cout<

cout<

else return 0;} void main(){ ElemType a,m;cout<<“请输入一个正整数:”<>a;cout<<“请输入要转换的进制:”<>m;SqStack as;as.f(a,m);}

西华大学数计学院学生上机实践报告

五、总结

通过本次实验，我熟悉了链表的操作，了解了线性表在现实生活中的运用，认识了顺序存储和链式存储这两种结构。本次上机实践基本完成了实验内容，但完成的不是很好，以后需要更加努力地掌握基本的知识。实验内容对于队列的运用没有涉及，希望以后有所涉及。

西华大学数计学院学生上机实践报告