數(shù)據(jù)結(jié)構(gòu)驗(yàn)證作業(yè)

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

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

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

4、; 2、查找"cout<<" 3、刪除"cout<<" 4、刪除重復(fù)結(jié)點(diǎn)"cout<<" 5、刪除偶數(shù)結(jié)點(diǎn)"cout<<" 6、構(gòu)建循環(huán)鏈表"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<<"您查找的數(shù)據(jù)在第"<<i-1<<"個位置."<<endl;j=1;p=p->next;if(j!=1)cout<<"您查

7、找的數(shù)據(jù)不在線性表中."<<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) / 刪除相同元素并釋放內(nèi)存 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<<"已經(jīng)變?yōu)檠h(huán)鏈表，其他操作將受影響,程序結(jié)束！"<<

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<<"當(dāng)前線性表為："<<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<<"當(dāng)前線性表為："<<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、刪除重復(fù)結(jié)點(diǎn)"cout<<" 5、刪除偶數(shù)結(jié)點(diǎn)"cout<<" 6、構(gòu)建循環(huán)鏈表"cout<<" 7、分解為兩個鏈表"cout<<" 0、退出"cout<<endl;cin>>k;if(k=1)cout<<"請輸入您要插入的數(shù)據(jù)值："cin>>a;cout<<"請輸入您要插入的位置："cin>>

14、i;p=ins(l,a,i);q=print(l);else if(k=2)cout<<"請輸入您要查找的數(shù)據(jù)值："cin>>a;p=find(l,a);q=print(l);else if(k=3) cout<<"請輸入您要刪除的數(shù)據(jù)的位置："cin>>i;p=del(l,i);q=print(l);else if(k=4) cout<<"刪除重復(fù)結(jié)點(diǎn)后的"p=delrepeat(l);q=print(l);else if(k=5) cout<<"刪除偶數(shù)結(jié)點(diǎn)后的"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個整數(shù)："<<endl;int c