本人正在学习数据结构，以下代码都是自己亲自写出来的，虽然有些代码写得不是很好，但是每个函数都是根据自己的思路写出来的。数据结构学的时间也不是很短了，刚开始不会应用到程序里。现在会了，觉得学习数据结构最重要的一点是，必须理解所学的算法，然后才能运用到程序中。同学看了我的程序说我写的程序跟别人的不一样。说我从特殊到一般来写的。说句实话，如果我没有思路，我绝对写不出程序。可能是不理解，或者是自己爱钻牛角尖吧，或者是自己太笨吧。。。不管怎么样，我都不会放弃的，我会努力吃透的。。。嘿嘿！！
#include<stdio.h>
typedef int ElemType;
typedef struct LNode{
ElemType data;
struct LNode *next;
}LNode,*LinkList;
LinkList createListL(LinkList head,int n);
LinkList createListH(LinkList head,int n);
LinkList traveral(LinkList head);
LinkList transpose(LinkList head);
LinkList transpose2(LinkList head, int size);
LinkList DelOuShu(LinkList head);
void separate(LinkList head,LinkList head1);
LinkList add_CreatL(LinkList head,int n);
LinkList merge(LinkList head3,LinkList head1,LinkList head2);
int main(void){
LinkList head,head1,head2,head3;
int n,num;
head=(LinkList)malloc(sizeof(LNode));
head1=(LinkList)malloc(sizeof(LNode));
head2=(LinkList)malloc(sizeof(LNode));
head3=(LinkList)malloc(sizeof(LNode));
head->next=NULL;
printf("(1) 随机产生或键盘输入一组元素序列，建立一个带头结点的单向链表（无序）；\n");
printf("(2) 遍历单向链表（即显示顺序表）；\n");
printf("三选一：\n");
printf("(3) 把单向链表中元素逆置（不允许申请新的结点空间）；\n");
printf("(4) 在单向链表中删除所有的偶数元素结点；\n");
printf("(5) 实现将单向链表其分解成两个链表，其中一个全部为奇数，另一个全部为偶数（尽量利用已知的存储空间）；\n");
printf("附加题：\n");
printf("(6) 编写在非递减有序链表中插入一个元素使链表元素仍有序的函数，并利用该函数建立一个非递减有序单向链表；\n");
printf("(7) 利用上题算法建立两个非递减有序单向链表，然后合并成一个非递增链表；\n");
while(num!=0){
printf("请选择：\n");
scanf("%d",&num);
switch(num){
case 1:
printf("请输入插入元素的个数：");
scanf("%d",&n);
head=createListH(head,n);break;
case 2:
head=createListH(head,n);
printf("\n");
traveral(head);break;
case 3:
printf("逆置后的顺序为：\n");
head=transpose(head);
traveral(head);break;
case 4:
printf("请输入链表元素的个数：");
scanf("%d",&n);
head=createListL(head,n);
traveral(head);
printf("\n");
head=DelOuShu(head);
traveral(head);break;
case 5:
printf("请输入链表元素的个数：");
scanf("%d",&n);
head=createListL(head,n);
traveral(head);
separate(head,head1);break;
case 6:
printf("请输入链表元素的个数：");
scanf("%d",&n);
head=add_CreatL(head,n);
traveral(head);break;
case 7:
printf("请输入链表元素的个数：");
scanf("%d",&n);
head1=add_CreatL(head1,n);
traveral(head1);
printf("请输入链表元素的个数：");
scanf("%d",&n);
head2=add_CreatL(head2,n);
traveral(head2);
head3=merge(head3,head1,head2);
printf("hao");
traveral(head3);
}
}
}
//(1) 随机产生或键盘输入一组元素序列，建立一个带头结点的单向链表（无序）；
LinkList createListH(LinkList head,int n){
LinkList ns ;
int i;
head=(LinkList)malloc(sizeof(LNode));
head->next=NULL;
//printf("随机产生3个数字：");
for(i=0;i<n;i++){
ns=(LinkList)malloc(sizeof(LNode));
ns->data=rand()%100+1;
ns->next=head->next;
head->next=ns;
printf("%d",ns->data);
printf("\n");
}
return head;
}
LinkList createListL(LinkList head,int n){
LinkList r,s;
int i;
head=(LinkList)malloc(sizeof(LNode));
r=head;
//head->next=NULL;
for(i=0;i<n;i++){
s=(LinkList)malloc(sizeof(LNode));
s->data=rand()%100+1;
r->next=s;
r=s;
//printf("%d",s->data);
//printf("\n");
}
r->next=NULL;
return head;
}
//(2) 遍历单向链表（即显示顺序表）；
LinkList traveral(LinkList head){
LinkList p;
//head=(LinkList)malloc(sizeof(LNode));
p=head->next;
while(p){
printf("%d",p->data);
p=p->next;
printf("\n");
}
}
//单链表的逆置
LinkList transpose(LinkList head){
LinkList q,p,r,s;
if(head==NULL||head->next==NULL){
return NULL;
}
s=head->next;
r=s->next;
p=s->next;
while(r){
q=head->next;
head->next=r;
s->next=r->next;
p=r;
r=r->next;
p->next=q;
}
return head;
}
LinkList transpose2(LinkList head, int size){
int i;
LinkList point[size],s;
point[0]=head->next;
s=head->next;
for(i=1;i<=size-1;i++){
point[i]=s->next;
printf("dizhi=%d\t",point[i]->data);
s=s->next;
//point[i]->next=point[i-1];
}
for(i=size-1;i>0;i--){
point[i]->next=point[i-1];
printf("dizhi=%d\t",point[i]->data);
}
point[0]->next=NULL;
head->next = point[size-1];
return head;
}
//(2) 在单向链表中删除所有的偶数元素结点；
LinkList DelOuShu(LinkList head){
LinkList p,r;
if(head==NULL||head->next==NULL){
return NULL;
}
p=head;
while(p->next!=NULL){
if(p->next->data%2==0){
r=p->next;
p->next=r->next;
free(r);
}
else
{
p=p->next;
}
}
return head;
}
//(3) 实现将单向链表其分解成两个链表，其中一个全部为奇数，另一个全部为偶数（尽量利用已知的存储空间）；
void separate(LinkList head,LinkList head1){
LinkList p,q,s,r;
p=head;
r=head1;
while(p->next!=NULL){
if(p->next->data%2==0){
s=(LinkList)malloc(sizeof(LNode));
s->data=p->next->data;
p->next=p->next->next;
r->next=s;
r=s;
}
else{
p=p->next;
}
}
r->next=NULL;
printf("变换后的奇数序列：\n");
traveral(head);
printf("\n");
printf("变换后的偶数序列：\n");
traveral(head1);
}
//(1) 编写在非递减有序链表中插入一个元素使链表元素仍有序的函数，并利用该函数建立一个非递减有序单向链表；
LinkList add_CreatL(LinkList head,int n){
LinkList s,r,p;
int i,num;
num=n;
r=head;
s=(LinkList)malloc(sizeof(LNode));
s->data=rand()%100+1;
s->next=NULL;
r->next=s;
r=s;
for(i=1;i<num;i++){
s=(LinkList)malloc(sizeof(LNode));
s->data=rand()%100+1;
s->next=NULL;
if(s->data>=r->data){
r->next=s;
r=s;
}
else{
p=head;
while(p->next!=NULL){
if(s->data>=p->next->data){
p=p->next;
}
else{
break;
}
}
s->next=p->next;
p->next=s;
}
}
return head;
}
//(7) 利用上题算法建立两个非递减有序单向链表，然后合并成一个非递增链表；
LinkList merge(LinkList head3,LinkList head1,LinkList head2){
LinkList r,s,k,p;
r=head1->next;
k=head2->next;
head3=(LinkList)malloc(sizeof(LNode));
head3->next=NULL;
while(r && k){
if(r->data>=k->data){
s=(LinkList)malloc(sizeof(LNode));
s->data=k->data;
k=k->next;
}
else{
s=(LinkList)malloc(sizeof(LNode));
s->data=r->data;
r=r->next;
}
s->next=head3->next;
head3->next=s;
}
while(r){
s=(LinkList)malloc(sizeof(LNode));
s->data=r->data;
r=r->next;
s->next=head3->next;
head3->next=s;
}
while(k){
s=(LinkList)malloc(sizeof(LNode));
s->data=k->data;
k=k->next;
s->next=head3->next;
head3->next=s;
}
return head3;
}