建立单链表

专业班级 信息101 学号 201012030119 姓名 刘丹 报告日期 2012/12/8.

1.1 预备知识

1.11 建立动态链表的存储结构形式及其描述。 1.12 单链表的建立、查找、插入、和删除操作。

1.2 实验目的

1.21 掌握单链表的存储结构、及其形式的描述。 1.22 掌握单链表的建立、查找、插入和删除操作。

1.3 实验内容

1.31 编写函数，实现随机产生或键盘输入一组元素，建立一个带头结点的单链表（无序）。 1.32 编写函数，实现遍历单链表。

1.33 编写函数，实现把单链表中的元素逆置（不允许建立新的结点）。 1.34 编写函数，建立一个非递减的有序单链表。

1.35 编写函数，建立连个非递减的有序但序列，然后合成一个非递减表。 1.36 编写函数，实现在非递减有序链表中插入一个元素，使表仍然有序。 1.37 编写函数，实现在非递减有序数列中删除值为X的结点。

1.38 编写一个主函数，在主函数中分别设计一个简单的菜单，分别调试他们。

1.4 编写程序

（1）//头插法建立单链表 void creathead(linklist l){ Node *s; int flag=1;

while(flag){ c=getchar(); }

if(c!='$'){ s=(Node*)malloc(sizeof(Node));

s->data=c;

s->next=l->next; l->next=s;

}

else flag=0;

}

（2）/遍历效果 void view(linklist l){ Node *s;

s=l->next;

while(s!=NULL){ cout<data<<\" \"; s=s->next; }

}

（3）//就地逆置 void revise(linklist l){ Node *p,*q;

p=l->next; l->next=NULL; while(p!=NULL){

q=p->next;

p->next=l->next; l->next=p; p=q;

} }

（4）//插入程序

elemtype e;

void inslist(linklist l,int i){

Node *pre,*s;

cout<<\"please insert position and value:\"; cin>>i; cin>>e;

int k;

if(i<=0) cout<<\"error\"; pre=l->next;k=0;

while(pre!=NULL&&knext; }

k++;

s=(Node*)malloc(sizeof(Node)); s->data=e;

s->next=pre->next; pre->next=s;

}

（5）//合并两个链表

void MergeList(linklist la,linklist lb,linklist lc){

Node *pa,*pb,*r; r=lc;

pa=la->next; pb=lb->next;

while(pa!=NULL && pb!=NULL){

}

if(pa->data<=pb->data){ r->next=pa; r=pa; pa=pa->next; }else{ r->next=pb; r=pb; }

if(pa) r->next=pa; else r->next=pb; free(la); free(lb);

pb=pb->next;

}

（6）//删除特定元素

void erase(linklist L,elemtype e){ Node *pre;

pre=L->next;

while(pre->next!=NULL && pre->next->data!=e){ pre=pre->next; }

if(pre->next){

Node *tem; tem=pre->next;

pre->next=pre->next->next; free(tem);

}

else printf(\"所要删除的元素不存在!\\n\");

} （7）int main(){ cout<<\" 菜单 \"<cout<<\"1.随机盘输入一组元素，建立头插法无序的单链表，以输出的形式遍历单链表\"<cout<<\"4.用尾插法建立链表并实现就地逆置\"<//调用初始化程序

cout<<\"please select a number:\";

int m; cin>>m; switch(m){

case 1: cout<<\"please input some characters:\"<cout<cout<<\"头插法建立链表显示:\"<cout<<\"please input some characters:\"<cout<<\"头插法建立链表逆置显示:\"<cout<<\"please input some characters:\"<cout<<\"尾插法建立链表显示:\"<cout<<\"please input some characters:\"<cout<<\"尾插法建立链表逆置显示:\"<break;

cout<<\"please input some characters:\"<creattail(n);

cout<<\"尾插法建立链表显示:\"<break;

cout<<\"建立第一个链表la:\"; creattail(la); cout<//调用就地逆置程序

case 2:

case 3:

case 4:

case 5:

case 6:

cout<<\"建立第二个链表lb:\"; creattail(lb);

cout<<\"合并链表\"<MergeList(la,lb,lc); view(lc); }

case 7:

break;

cout<<\"删除特定元素\"<cout<cout<<\"输入删除的数:\"; cin>>e; erase(la,e); view(la);

break; case 10: exit(1);

default:cout<<\"error\"<return 0;

1,5调试结果

（1）建立链表

1.51建立链表

（2）遍历效果

（3）头插法就地逆置

1.52头插法建立链表显示

1.52头插法就地逆置

（4）建立非递减序列并插入一个数

1.54建立非递减序列并插入一个数

（5）合并两个递减链表

（6）删除一个元素

1.55合并两个递减链表

（7）菜单页面

1.56删除一个元素

1.57菜单页面

1.6 实验心得

本次试验是建立单链表，并了解单链表的插入、删除、合并的基本操作，在实验刚开始的时候，由于对于c不是很灵活所以有很多程序命令不会用，所以本实验中很多实验都是有c++和c的集成体。不过在同学们的帮助下，渐渐熟悉了结构体和指针，然后经过反复调试和修改终于完成了实验