編寫一個完整的程序，實現單鏈表的建立、插入、刪除、輸出等基本操作。
（1）建立一個帶頭結點的單鏈表。
（2）計算單鏈表的長度，然後輸出單鏈表。
（3）查找值為x的直接前驅結點q。
（4）刪除值為x的結點。
（5）把單向鏈表中元素逆置（不允許申請新的結點空間）。
（6）已知單鏈表中元素遞增有序，請寫出一個高效的算法，刪除表中所有值大於mink且小於maxk的元素（若表中存在這樣的元素），同時釋放被刪結點空間，並分析你的算法的時間復雜度（注意：mink和maxk是給定的兩個參變量，他們的值可以和表中的元素相同，也可以不同）。
（7）同（6）的條件，試寫一高效的算法，刪除表中所有值相同的多余元素（使得操作後的線性表中所有元素的值均不相同），同時釋放被刪結點空間，並分析你的算法時間復雜度。
（8）利用（1）建立的鏈表，實現將其分解成兩個鏈表，其中一個全部為奇數，另一個全部為偶數（盡量利用已知的存儲空間）。
（9）在主函數中設計一個簡單的菜單，分別測試上述算法。
[cpp]
//因為沒有要求輸入的鏈表數據的數量，所以我用-1表示輸入結束。
//測試數據 1 2 3 4 5 6 -1
//測試刪除相同元素的數據 2 2 3 3 4 4 5 5
#include<stdio.h>
#include<stdlib.h>
struct node
{
int data;
node *next;
};
node *h,*h1,*h2;
void Creatlist()//創建鏈表
{
node *s,*e;
h=(node *)malloc(sizeof(node));
s=(node *)malloc(sizeof(node));
h->next=s;
printf("請輸入單鏈表數據： ");
scanf("%d",&s->data);
e=h;
while(s->data!=-1)//用-1表示鏈表輸入終止
{
e=s;
s=(node *)malloc(sizeof(node));
scanf("%d",&s->data);
e->next=s;
}
e->next=NULL;
return ;
}
void Printlist(node *h)//輸出鏈表
{
int count;
node *s;
s=h;
count=0;
while(s->next!=NULL)//先遍歷一遍，用count記錄鏈表的長度。
{
count++;
s=s->next;
}
printf("單鏈表長度： %d\n",count);
if(count==0)
{
printf("鏈表為空！\n");
return ;
}
printf("單鏈表數據： ");
s=h;
while(s->next!=NULL)
{
s=s->next;
printf("%d ",s->data);
}
printf("\n");
return ;
}
void Findlist()//查找值為x的前驅結點
{
int x;
node *s,*e;
printf("請輸入待查找的數值： ");
scanf("%d",&x);
s=h->next;
if(s->data==x)
{
printf("%d沒有前驅結點！\n",x);//x為第一個結點
return ;
}
e=s->next;
while(e->data!=x&&e->next!=NULL)
{
s=e;
e=s->next;
}
if(e->data!=x)
{
printf("單鏈表中不存在值為%d的結點！\n",x);//鏈表中沒有x
return ;
}
printf("%d的前驅結點為： %d\n",x,s->data);
return ;
}
void Deletlist()//刪除值為x的結點，實驗中沒有要求，我寫的時候是按鏈表中只有一個值為x的結點。
{
int x;
node *s,*e;
printf("請輸入需要刪除的數值： ");
scanf("%d",&x);
s=h;
e=s->next;
while(e->data!=x&&e->next!=NULL)
{
s=e;
e=s->next;
}
if(e->data!=x)
{
printf("單鏈表中不存在值為%d的結點！\n",x);//鏈表中沒有值為x的結點
return ;
}
s->next=e->next;
free(e);
return ;
}
void Inverlist()//逆置鏈表，將連接鏈表的指針方向倒轉，不需要申請新的空間。
{
node *s,*e,*r;
s=h->next;
e=s->next;
if(e==NULL)
{
h->next=s;
return ;
}
s->next=NULL;
r=e->next;
while(e!=NULL)
{
e->next=s;
s=e;
e=r;
if(e==NULL)
break;
r=e->next;
}
h->next=s;
return ;
}
void Delexylist()//刪除鏈表中x和y之間的數字，而且要求釋放內存。既然要求釋放內存，那就只能遍歷，我沒想到什麼更高效的算法，因為鏈表是有序的，我釋放到值為y結束。
{
int x,y;
node *s,*e,*r;
printf("請輸入需要刪除的區間 ");
scanf("%d %d",&x,&y);
r=h;
s=h->next;
while(s->data<=y&&s->next!=NULL)
{
e=s->next;
if(s->data>=x)
{
free(s);
r->next=e;
}
else
r=s;
s=e;
}
return ;
}
void DeleSamelist()//刪除相同元素的結點同時釋放內存空間。同樣需要遍歷，沒有想到特別高效的算法。
{
int temp;
node *s,*e,*r;
r=h;
s=h->next;
if(s==NULL)
return ;
temp=-1;
while(s!=NULL)
{
e=s->next;
if(s->data==temp)
{
free(s);
r->next=e;
}
else
{
temp=s->data;
r=s;
}
s=e;
}
return ;
}
void Cutlist()//分拆鏈表。
{
node *s,*s1,*e1,*s2,*e2;
h1=(node *)malloc(sizeof(node));
s1=(node *)malloc(sizeof(node));
h2=(node *)malloc(sizeof(node));
s2=(node *)malloc(sizeof(node));
e1=h1;
e1->next=NULL;
e2=h2;
e2->next=NULL;
s=h->next;
while(s!=NULL)
{
if(s->data%2!=0)
{
s1->data=s->data;
e1->next=s1;
e1=s1;
e1->next=NULL;
s1=(node *)malloc(sizeof(node));
}
else
{
s2->data=s->data;
e2->next=s2;
e2=s2;
e2->next=NULL;
s2=(node *)malloc(sizeof(node));
}
s=s->next;//第一次寫的時候沒有加上這一句，電腦直接就卡死了。。。。
}
Printlist(h1);
Printlist(h2);
return ;
}
int Opra()
{
int T;
printf("*****************目錄******************\n");
printf("創建一個單鏈表： 1\n");
printf("計算單鏈表長度並輸出單鏈表： 2\n");
printf("查找值為x的前驅結點： 3\n");
printf("刪除值為x的結點： 4\n");
printf("把單鏈表中的元素逆置： 5\n");
printf("刪除單鏈表中值在x和y之間的元素： 6\n");
printf("刪除鏈表中值相同的元素： 7\n");
printf("將鏈表分成兩部分： 8\n");
printf("操作結束： 0\n");
printf("輸入操作代號： ");
scanf("%d",&T);
switch(T)
{
case 1:Creatlist();break;
case 2:Printlist(h);break;
case 3:Findlist(); break;
case 4:Deletlist();break;
case 5:Inverlist();break;
case 6:Delexylist();break;
case 7:DeleSamelist();break;
case 8:Cutlist();break;
case 0:return 0;
default :printf("輸入錯誤，請重新輸入！\n");break;
}
return 1;
}
int main()
{
int flag=1;
while(1)
{
flag=Opra();
if(!flag)//用flag控制是否跳出循環。
break;
printf("\n\n");
}
printf("謝謝使用！\n");
return 0;
}
//因為沒有要求輸入的鏈表數據的數量，所以我用-1表示輸入結束。
//測試數據 1 2 3 4 5 6 -1
//測試刪除相同元素的數據 2 2 3 3 4 4 5 5
#include<stdio.h>
#include<stdlib.h>
struct node
{
int data;
node *next;
};
node *h,*h1,*h2;
void Creatlist()//創建鏈表
{
node *s,*e;
h=(node *)malloc(sizeof(node));
s=(node *)malloc(sizeof(node));
h->next=s;
printf("請輸入單鏈表數據： ");
scanf("%d",&s->data);
e=h;
while(s->data!=-1)//用-1表示鏈表輸入終止
{
e=s;
s=(node *)malloc(sizeof(node));
scanf("%d",&s->data);
e->next=s;
}
e->next=NULL;
return ;
}
void Printlist(node *h)//輸出鏈表
{
int count;
node *s;
s=h;
count=0;
while(s->next!=NULL)//先遍歷一遍，用count記錄鏈表的長度。
{
count++;
s=s->next;
}
printf("單鏈表長度： %d\n",count);
if(count==0)
{
printf("鏈表為空！\n");
return ;
}
printf("單鏈表數據： ");
s=h;
while(s->next!=NULL)
{
s=s->next;
printf("%d ",s->data);
}
printf("\n");
return ;
}
void Findlist()//查找值為x的前驅結點
{
int x;
node *s,*e;
printf("請輸入待查找的數值： ");
scanf("%d",&x);
s=h->next;
if(s->data==x)
{
printf("%d沒有前驅結點！\n",x);//x為第一個結點
return ;
}
e=s->next;
while(e->data!=x&&e->next!=NULL)
{
s=e;
e=s->next;
}
if(e->data!=x)
{
printf("單鏈表中不存在值為%d的結點！\n",x);//鏈表中沒有x
return ;
}
printf("%d的前驅結點為： %d\n",x,s->data);
return ;
}
void Deletlist()//刪除值為x的結點，實驗中沒有要求，我寫的時候是按鏈表中只有一個值為x的結點。
{
int x;
node *s,*e;
printf("請輸入需要刪除的數值： ");
scanf("%d",&x);
s=h;
e=s->next;
while(e->data!=x&&e->next!=NULL)
{
s=e;
e=s->next;
}
if(e->data!=x)
{
printf("單鏈表中不存在值為%d的結點！\n",x);//鏈表中沒有值為x的結點
return ;
}
s->next=e->next;
free(e);
return ;
}
void Inverlist()//逆置鏈表，將連接鏈表的指針方向倒轉，不需要申請新的空間。
{
node *s,*e,*r;
s=h->next;
e=s->next;
if(e==NULL)
{
h->next=s;
return ;
}
s->next=NULL;
r=e->next;
while(e!=NULL)
{
e->next=s;
s=e;
e=r;
if(e==NULL)
break;
r=e->next;
}
h->next=s;
return ;
}
void Delexylist()//刪除鏈表中x和y之間的數字，而且要求釋放內存。既然要求釋放內存，那就只能遍歷，我沒想到什麼更高效的算法，因為鏈表是有序的，我釋放到值為y結束。
{
int x,y;
node *s,*e,*r;
printf("請輸入需要刪除的區間 ");
scanf("%d %d",&x,&y);
r=h;
s=h->next;
while(s->data<=y&&s->next!=NULL)
{
e=s->next;
if(s->data>=x)
{
free(s);
r->next=e;
}
else
r=s;
s=e;
}
return ;
}
void DeleSamelist()//刪除相同元素的結點同時釋放內存空間。同樣需要遍歷，沒有想到特別高效的算法。
{
int temp;
node *s,*e,*r;
r=h;
s=h->next;
if(s==NULL)
return ;
temp=-1;
while(s!=NULL)
{
e=s->next;
if(s->data==temp)
{
free(s);
r->next=e;
}
else
{
temp=s->data;
r=s;
}
s=e;
}
return ;
}
void Cutlist()//分拆鏈表。
{
node *s,*s1,*e1,*s2,*e2;
h1=(node *)malloc(sizeof(node));
s1=(node *)malloc(sizeof(node));
h2=(node *)malloc(sizeof(node));
s2=(node *)malloc(sizeof(node));
e1=h1;
e1->next=NULL;
e2=h2;
e2->next=NULL;
s=h->next;
while(s!=NULL)
{
if(s->data%2!=0)
{
s1->data=s->data;
e1->next=s1;
e1=s1;
e1->next=NULL;
s1=(node *)malloc(sizeof(node));
}
else
{
s2->data=s->data;
e2->next=s2;
e2=s2;
e2->next=NULL;
s2=(node *)malloc(sizeof(node));
}
s=s->next;//第一次寫的時候沒有加上這一句，電腦直接就卡死了。。。。
}
Printlist(h1);
Printlist(h2);
return ;
}
int Opra()
{
int T;
printf("*****************目錄******************\n");
printf("創建一個單鏈表： 1\n");
printf("計算單鏈表長度並輸出單鏈表： 2\n");
printf("查找值為x的前驅結點： 3\n");
printf("刪除值為x的結點： 4\n");
printf("把單鏈表中的元素逆置： 5\n");
printf("刪除單鏈表中值在x和y之間的元素： 6\n");
printf("刪除鏈表中值相同的元素： 7\n");
printf("將鏈表分成兩部分： 8\n");
printf("操作結束： 0\n");
printf("輸入操作代號： ");
scanf("%d",&T);
switch(T)
{
case 1:Creatlist();break;
case 2:Printlist(h);break;
case 3:Findlist(); break;
case 4:Deletlist();break;
case 5:Inverlist();break;
case 6:Delexylist();break;
case 7:DeleSamelist();break;
case 8:Cutlist();break;
case 0:return 0;
default :printf("輸入錯誤，請重新輸入！\n");break;
}
return 1;
}
int main()
{
int flag=1;
while(1)
{
flag=Opra();
if(!flag)//用flag控制是否跳出循環。
break;
printf("\n\n");
}
printf("謝謝使用！\n");
return 0;
}
