1、數據結構實驗報告一一、上機實驗的問題和要求：單鏈表的查找、插入與刪除。設計算法，實現線性結構上的單鏈表的產生以及元素的查找、插入與刪除。具體實現要求：1. 從鍵盤輸入20個整數，產生不帶表頭的單鏈表，并輸入結點值。2. 從鍵盤輸入1個整數，在單鏈表中查找該結點的位置。若找到，則顯示“找到了”；否則，則顯示“找不到”。3. 從鍵盤輸入2個整數，一個表示欲插入的位置i，另一個表示欲插入的數值x，將x插入在對應位置上，輸出單鏈表所有結點值，觀察輸出結果。4. 從鍵盤輸入1個整數，表示欲刪除結點的位置，輸出單鏈表所有結點值，觀察輸出結果。5. 將單鏈表中值重復的結點刪除，使所得的結果表中個結點值均不相

2、同，輸出單鏈表所有結點值，觀察輸出結果。6. 刪除其中所有數據值為偶數的結點，輸出單鏈表所有結點值，觀察輸出結果。7. 把單鏈表變成帶表頭結點的循環鏈表，輸出循環單鏈表所有結點值，觀察輸出結果。8. （）將單鏈表分解成兩個單鏈表A和B，使A鏈表中含有原鏈表中序號為奇數的元素，而B鏈表中含有原鏈表中序號為偶數的元素，且保持原來的相對順序，分別輸出單鏈表A和單鏈表B的所有結點值，觀察輸出結果。二、程序設計的基本思想，原理和算法描述：1、基本操作函數link * get(link *l, int i)； /創建鏈表link * ins (link *l, int a,int i)/在鏈表內插入值li

3、nk * find(link *l, int a)；/在鏈表內查找值link * del(link *l, int i);/在鏈表內刪除值link * delrepeat( link *l);/在鏈表內刪除重復值link * deleven(link *l);/刪除鏈表內偶數值link * rotate(link *l);/形成循環鏈表void divide(link *l);/分解成兩個鏈表cout<<endl;2、基本操作cout<<"請選擇您要的操作："cout<<" 1、插入"cout<<"

4、; 2、查找"cout<<" 3、刪除"cout<<" 4、刪除重復結點"cout<<" 5、刪除偶數結點"cout<<" 6、構建循環鏈表"cout<<" 7、分解為兩個鏈表"cout<<" 0、退出"三、源程序及注釋：#include <iostream>using namespace std;typedef struct nodeint data;struct node *ne

5、xt;link;void print1(link *l);link * get(link *l, int i)link *p;int j=0;p=l;while(j<i) && (p->next!=NULL)p=p->next;j+;if(j=i)return p;elsereturn NULL;link * ins (link *l, int a,int i) link *p,*s;p=get(l,i-1);if(p=NULL)cout<<"輸入有誤"<<endl;elses=(link *)malloc(size

6、of(link);s->data=a;s->next=p->next;p->next=s;return l;link * find(link *l, int a)link *p; int i=0;int j=0;p=l;while(p!=NULL) i+;if(p->data!=a)p=p->next;else cout<<"您查找的數據在第"<<i-1<<"個位置."<<endl;j=1;p=p->next;if(j!=1)cout<<"您查

7、找的數據不在線性表中."<<endl;return l;link * del(link *l, int i)link *p,*s; p=get(l,i-1);if(p=NULL)cout<<"輸入有誤"<<endl;elses=p->next;p->next=s->next;free(s);return l;link * delrepeat( link *l) / 刪除相同元素并釋放內存 link *s, *r, *t; if ( l-> next = NULL ) return l; s = l->

8、; next; while ( s-> next ) t = s; r = s-> next; while ( t-> next ) if ( s-> data = r-> data ) t-> next = r-> next; free(r); r = t-> next; else t = t-> next; r = t-> next; s = s-> next; if ( !s ) return l; return l; link * deleven(link *l) link *q=l;link *p=l->next

9、; while(p)if(p->data%2=0)link *r=p;q->next=p->next;p=p->next;free(r);elsep=p->next;q=q->next;return l;link * rotate(link *l) link * p=l;while(p->next)p=p->next;p->next=l; link * t=l->next;while(t!=l)t=t->next;cout<<"已經變為循環鏈表，其他操作將受影響,程序結束！"<<

10、9;n'return l;void divide(link *l) link * a=l;link * b=(link *)malloc(sizeof(node);b->next=NULL;link *Lb=b; int i=1; link * La=l;link * p=l->next;while(p) if(i+%2=0) La->next=p->next;p->next=NULL;Lb->next=p;Lb=Lb->next;p=La->next;elsep=p->next;La=La->next;cout<<

11、;"鏈表a" print1(a); cout<<"鏈表b" print1(b); void print1(link *l) int i,k;int a;link *p,*q;cout<<"當前線性表為："<<endl;p=l;p=p->next;if(l!=NULL)do cout<<p->data<<" "p=p->next;while(p!=NULL);cout<<endl;link * print(link *l) in

12、t i,k;int a;link *p,*q;cout<<"當前線性表為："<<endl;p=l;p=p->next;if(l!=NULL)do cout<<p->data<<" "p=p->next;while(p!=NULL);cout<<endl;cout<<"請選擇您要的操作："cout<<" 1、插入"cout<<" 2、查找"cout<<" 3、刪除

13、"cout<<" 4、刪除重復結點"cout<<" 5、刪除偶數結點"cout<<" 6、構建循環鏈表"cout<<" 7、分解為兩個鏈表"cout<<" 0、退出"cout<<endl;cin>>k;if(k=1)cout<<"請輸入您要插入的數據值："cin>>a;cout<<"請輸入您要插入的位置："cin>>

14、i;p=ins(l,a,i);q=print(l);else if(k=2)cout<<"請輸入您要查找的數據值："cin>>a;p=find(l,a);q=print(l);else if(k=3) cout<<"請輸入您要刪除的數據的位置："cin>>i;p=del(l,i);q=print(l);else if(k=4) cout<<"刪除重復結點后的"p=delrepeat(l);q=print(l);else if(k=5) cout<<"刪除偶數結點后的"p=deleven(l);q=print(l);else if(k=6)p=rotate(l);q=print(l);else if(k=7)divide(l);else if(k=0);elsecout<<"輸入錯誤!"<<endl;return l;int main()cout<<"請輸入20個整數："<<endl;int c