數(shù)據(jù)結構實驗二

1、數(shù)據(jù)結構實驗報告二學校： 班級： 學號： 姓名： 日期： 程序名： 一、上機實驗的問題和要求：單鏈表的查找、插入與刪除。設計算法，實現(xiàn)線性結構上的單鏈表的產(chǎn)生以及元素的查找、插入與刪除。具體實現(xiàn)要求：1. 從鍵盤輸入20個整數(shù)，產(chǎn)生不帶表頭的單鏈表，并輸入結點值。2. 從鍵盤輸入1個整數(shù)，在單鏈表中查找該結點的位置。若找到，則顯示“找到了”；否則，則顯示“找不到”。3. 從鍵盤輸入2個整數(shù)，一個表示欲插入的位置i，另一個表示欲插入的數(shù)值x，將x插入在對應位置上，輸出單鏈表所有結點值，觀察輸出結果。4. 從鍵盤輸入1個整數(shù)，表示欲刪除結點的位置，輸出單鏈表所有結點值，觀察輸出結果。5. 將單鏈表

2、中值重復的結點刪除，使所得的結果表中個結點值均不相同，輸出單鏈表所有結點值，觀察輸出結果。6. 刪除其中所有數(shù)據(jù)值為偶數(shù)的結點，輸出單鏈表所有結點值，觀察輸出結果。7. 把單鏈表變成帶表頭結點的循環(huán)鏈表，輸出循環(huán)單鏈表所有結點值，觀察輸出結果。8. （）將單鏈表分解成兩個單鏈表A和B，使A鏈表中含有原鏈表中序號為奇數(shù)的元素，而B鏈表中含有原鏈表中序號為偶數(shù)的元素，且保持原來的相對順序，分別輸出單鏈表A和單鏈表B的所有結點值，觀察輸出結果。二、程序設計的基本思想，原理和算法描述：（包括程序的結構，數(shù)據(jù)結構，輸入/輸出設計，符號名說明等） 這是一個帶頭結點的線性鏈表，數(shù)據(jù)域存放整形數(shù)據(jù)，由用戶輸入

3、。頭結點數(shù)據(jù)域存鏈表長度，所以程序中有個求鏈表長度的函數(shù) int LengthList(LinkList L); /求鏈表長度L是指向頭結點的指針，將長度值存入語句為 L->data = LengthList(L);為了實時觀察鏈表情況，程序中有個輸出鏈表數(shù)據(jù)的函數(shù) void PrintList(LinkList L); /輸出鏈表程序可以實現(xiàn)8種不同的操作，這8種不同的操作由8個函數(shù)實現(xiàn)，分別是void CreateList(LinkList &L); /創(chuàng)建鏈表void Locate(LinkList L); /查詢數(shù)值void InsertList(LinkList &am

4、p;L); /插入數(shù)值void DeleteList(LinkList &L); /選擇刪除void Deleterepeat(LinkList &L); /刪除重復結點void DeleteEven(LinkList &L); /刪除數(shù)值為偶數(shù)的結點void Rotate(LinkList &L); /變?yōu)檠h(huán)鏈表void Divide(LinkList &L); /分解成兩個鏈表 這些基本操作的實現(xiàn)算法都比較簡單，有些跟書本上一樣，有些需要自己稍作思考才能寫出，具體程序見第三部分 8種不同的操作可以由用戶通過按A-H這八個字母鍵來選擇，分別是 A:創(chuàng)

5、建 B:查詢 C:插入 D:選擇刪除 E:刪除重復 F:刪除偶數(shù) G:變?yōu)檠h(huán)鏈表 H:分解為兩個鏈表，見第四部分輸出截圖，可以清晰的看到整個過程主程序中用 開關語句實現(xiàn):char operate;printf("nn輸入字符選擇鏈表操作類型nA:創(chuàng)建 B:查詢 C:插入 D:選擇刪除 E:刪除重復 F:刪除偶數(shù) nG:變?yōu)檠h(huán)鏈表 H:分解為兩個鏈表n");scanf("%c",&operate);switch (operate) case 'a': case 'A': CreateList(L);break;

6、case 'b': case 'B': Locate(L);break; case 'c': case 'C': InsertList(L); break; case 'd': case 'D': DeleteList(L);break; case 'e': case 'E': Deleterepeat(L);break; case 'f': case 'F': DeleteEven(L);break; case 'g'

7、: case 'G': Rotate(L);break; case 'h': case 'H': Divide(L);break; case 'n':goto label; default: printf("輸入有誤，請重新輸入！");break;3、 源程序及注釋：#include<stdio.h>#include<malloc.h>typedef struct LNode /鏈表結點int data;struct LNode *next;LNode,*LinkList; int ov

8、er_flag=0; /主函數(shù)結束標識符void CreateList(LinkList &L); /創(chuàng)建鏈表void Locate(LinkList L); /查詢數(shù)值void InsertList(LinkList &L); /插入數(shù)值void DeleteList(LinkList &L); /選擇刪除void Deleterepeat(LinkList &L); /刪除重復結點void DeleteEven(LinkList &L); /刪除數(shù)值為偶數(shù)的結點void Rotate(LinkList &L); /變?yōu)檠h(huán)鏈表void Div

9、ide(LinkList &L); /分解成兩個鏈表int LengthList(LinkList L); /求鏈表長度void PrintList(LinkList L); /輸出鏈表 /* 主函數(shù)*/void main(void) char operate;LinkList L;int n;for( n=0;n<40;n+)printf("nn輸入字符選擇鏈表操作類型nA:創(chuàng)建 B:查詢 C:插入 D:選擇刪除 E:刪除重復 F:刪除偶數(shù) nG:變?yōu)檠h(huán)鏈表 H:分解為兩個鏈表n"); label:scanf("%c",&ope

10、rate);switch (operate) case 'a': case 'A': CreateList(L);break; case 'b': case 'B': Locate(L);break; case 'c': case 'C': InsertList(L); break; case 'd': case 'D': DeleteList(L);break; case 'e': case 'E': Deleterepeat(L);

11、break; case 'f': case 'F': DeleteEven(L);break; case 'g': case 'G': Rotate(L);break; case 'h': case 'H': Divide(L);break; case 'n':goto label; /排除換行鍵的影響 default: printf("輸入有誤，請重新輸入！");break; if(over_flag)return; /* 創(chuàng)建鏈表*/void CreateLi

12、st(LinkList &L) int temp; printf("創(chuàng)建鏈表：n請輸入創(chuàng)建鏈表所需的整數(shù)值(以-1結束):"); L = (LinkList)malloc(sizeof(LNode); L->next = NULL; LinkList q=L; scanf("%d",&temp); while(temp!=-1) LinkList p; p = (LinkList)malloc(sizeof(LNode); p->data = temp; p->next = NULL; q->next = p; q

13、 = q->next; scanf("%d",&temp); L->data = LengthList(L); PrintList(L);/* 查詢元素*/void Locate(LinkList L) if(!L)printf("錯誤：鏈表未創(chuàng)建！");int element;printf("查詢數(shù)值：n輸入要查詢的數(shù)值："); scanf("%d",&element);LinkList p=L->next;int i =1; while(p) if(p->data=ele

14、ment) printf("找到了，它是鏈表的第%d個元素。n",i); return ; p=p->next; i+; printf("找不到。n");/* 插入數(shù)值*/void InsertList(LinkList &L) int x,i; printf("插入數(shù)值：n輸入要插入的數(shù)值和插入的位置："); scanf("%d",&x); scanf("%d",&i); LinkList p = L; int j = 0; while (p &&

15、 j < i-1) p = p->next; +j; if (!p | j > i-1) printf("輸入位置錯誤!") ; return; LinkList s = (LinkList)malloc(sizeof(LNode); s->data = x; s->next = p->next; p->next = s; L->data = LengthList(L); PrintList(L); /* 選擇位置刪除節(jié)點*/void DeleteList(LinkList &L) int i; LinkList p

16、= L; printf("選擇位置刪除結點：n輸入要刪除數(shù)值的位置："); scanf("%d",&i); int j = 0; while (p->next && j < i-1) p = p->next; +j; if (!(p->next) | j > i-1) printf("輸入位置錯誤!") ; return; LinkList q = p->next; p->next = q->next; free(q); L->data = LengthLi

17、st(L); PrintList(L); /* 刪除重復結點*/void Deleterepeat(LinkList &L) printf("刪除重復結點后的鏈表為：n");int n=1;int a20;LinkList q=L->next;LinkList p=q->next; a0=q->data;while(p)for(int i=0;i<n;i+)if(p->data=ai) LinkList r=p; q->next=p->next;p=p->next;free(r);break;if(i=n)an+=p-

18、>data; p=p->next;q=q->next; L->data = LengthList(L); PrintList(L);/* 刪除數(shù)值為偶數(shù)的結點*/void DeleteEven(LinkList &L) printf("刪除偶數(shù)結點后的鏈表為：n");LinkList q=L;LinkList p=L->next; while(p)if(p->data%2=0)LinkList r=p;q->next=p->next;p=p->next;free(r); else p=p->next;q=q

19、->next; L->data = LengthList(L); PrintList(L);/* 變?yōu)檠h(huán)鏈表*/void Rotate(LinkList &L) printf("變?yōu)檠h(huán)鏈表：n");LinkList p=L;while(p->next)p=p->next;p->next=L; LinkList t=L->next;printf("長度：%dt",L->data); printf("各個結點數(shù)值為：");while(t!=L)printf("%dt"

20、;,t->data); t=t->next; printf("n");printf("已經(jīng)變?yōu)檠h(huán)鏈表，其他操作將受影響,程序結束！n");over_flag=1;/* 分解成兩個鏈表*/void Divide(LinkList &L) printf("分解成兩個鏈表：n");LinkList A=L;LinkList B=(LinkList)malloc(sizeof(LNode);B->next=NULL;LinkList Lb=B; int i=1; LinkList La=L;LinkList p=L

21、->next;while(p) if(i+%2=0) La->next=p->next; p->next=NULL; Lb->next=p; Lb=Lb->next; p=La->next; else p=p->next; La=La->next; A->data = LengthList(A); printf("鏈表A:"); PrintList(A); B->data = LengthList(B); printf("鏈表B:"); PrintList(B); printf("

22、;已經(jīng)分解成兩個鏈表，其他操作將受影響,程序結束！n"); over_flag=1;/* 求鏈表長度*/int LengthList(LinkList L)int i=0;LinkList p=L->next;while(p)p=p->next;i+;return i;/* 輸出鏈表*/void PrintList(LinkList L) LinkList t=L->next;printf("長度：%dt",L->data); printf("結點數(shù)值：");while(t)printf("%dt",

23、t->data); t=t->next; printf("n");4、 運行輸出結果：5、 調試和運行程序過程中產(chǎn)生的問題及采取的措施： 1. 主程序中我用到 char operate; scanf("%c",&operate); Operate存放用戶選擇操作類型的字母A-H，但是當用戶鍵入字母后，要按ENTER 鍵 表示輸入完畢，所以以后執(zhí)行scanf("%c",&operate);是會把ENTER輸入到operate中，從而影響了后面的操作，解決方案是加一個標記位 label :scanf("

24、;%c",&operate);當程序發(fā)現(xiàn)輸入為ENTER時，回到labeL處，這樣解決了問題。請看下面語句，注意 case 'n':goto label;label : scanf("%c",&operate);switch (operate) case 'a': case 'A': CreateList(L);break; case 'b': case 'B': Locate(L);break; case 'c': case 'C': InsertList(L); break; case 'd': case 'D': DeleteList(L);break; case 'e': case 'E': Deleterepeat(L);break; case 'f': case 'F': DeleteEven(L);break; case 'g': case 'G': Rotate(L);break;