《鏈表的合并 實(shí)驗(yàn)報(bào)告#參考資料》由會員分享，可在線閱讀，更多相關(guān)《鏈表的合并 實(shí)驗(yàn)報(bào)告#參考資料（14頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。
1、
課程設(shè)計(jì)報(bào)告
課程設(shè)計(jì)題目：兩個(gè)鏈表的合并
專 業(yè)：軟件工程
班 級：
姓 名：
學(xué) 號:
指導(dǎo)教師:
年 月 日
目 錄
1. 課程設(shè)計(jì)的目的及要求
2. 課程設(shè)計(jì)的內(nèi)容（分析和設(shè)計(jì)）
3. 算法流程圖
4. 詳細(xì)步驟
5. 代碼
6. 顯示結(jié)果
7. 課程設(shè)計(jì)的總結(jié)
一．課程設(shè)計(jì)的目的及要求
1.目的：實(shí)現(xiàn)兩個(gè)鏈表的合并
2.要求：
（1） 建立兩個(gè)鏈表A和B，鏈表元素個(gè)數(shù)分別為m和n個(gè)。
2、
（2） 假設(shè)元素分別為(x1,x2,…xm)，和(y1,y2,?…yn)。把它們合并成一個(gè)線形表C，使得：
當(dāng)m>=n時(shí)，C=x1,y1,x2,y2,…xn,yn,…,xm
當(dāng)n>m時(shí)，C=y1,x1,y2,x2,…ym,xm,…,yn
輸出線形表C
（3） 用直接插入排序法對C進(jìn)行升序排序，生成鏈表D，并輸出鏈表D。
（4） 能刪除指定單鏈表中指定位子和指定值的元素。
二．課程設(shè)計(jì)的內(nèi)容（分析和設(shè)計(jì)）
1..分析
由題目的相關(guān)信息可以分析得：首先我們需要建立兩個(gè)鏈表AB，A鏈表的元素個(gè)數(shù)為m，B鏈表的元素個(gè)數(shù)為n；在將A、B鏈表進(jìn)行合并，根據(jù)m和n的大小關(guān)系決定鏈
3、表C的元素順序；再將C進(jìn)行直接插入排序得到一個(gè)新的鏈表D；沒次輸入完一次鏈表信息，程序都會對相應(yīng)的鏈表進(jìn)行輸入操作以此確保程序輸入的數(shù)據(jù)是你想要輸入的數(shù)據(jù)。同時(shí)當(dāng)你合并好和排序好后都會進(jìn)行輸出操作。最后當(dāng)排序好后你可以指定你所要?jiǎng)h除數(shù)據(jù)的位置來刪除你所要?jiǎng)h除的數(shù)據(jù)。
2.設(shè)計(jì)
本次課程設(shè)計(jì)所需要用到的是關(guān)于鏈表的建立、合并以及直接插入排序的排序算法。需要先建立兩個(gè)鏈表，再將其合并為一個(gè)無序鏈表，最后對這個(gè)無序鏈表進(jìn)行直接插入排序并將其輸出。難點(diǎn)在于將AB合并為鏈表C的操作以及對鏈表C進(jìn)行直接插入排序的操作和根據(jù)用戶的意愿可以對鏈表進(jìn)行刪除的操作。
三．算法流程圖
建立鏈表A
建立鏈表
4、B
合并A B鏈表
得到C鏈表
得到D鏈表
得到E鏈表
比較m.n
排序
刪除
四．詳細(xì)步驟
(1) 結(jié)構(gòu)體的創(chuàng)建：struct Node
(2) 鏈表的創(chuàng)建：struct Node *create（）鏈表的創(chuàng)建。
(3) 鏈表的輸出：void print(struct Node *head)功能是對鏈表進(jìn)行輸出。
(4) 鏈表的合并：struct Node * inter_link(struct Node * chain1, int a, struct Node * chain2, int b)
算法的功能是實(shí)現(xiàn)兩個(gè)鏈表的交叉合并，并且可以根據(jù)兩鏈
5、表的長短將行不通的插入。
(5) 排序：void InsertSort(struct Node *p,int m)算法的功能是對一合并好的鏈表進(jìn)行升序插入排序。
(6) 按位刪除操作：struct Node * delete_link(struct Node *p,int i)。
(7) 按值刪除操作：struct Node * delete_linkz(struct Node *p,int i)。
(8) 主函數(shù)：main()函數(shù)主要是對算法進(jìn)行測試。
五．代碼
struct Node //數(shù)據(jù)結(jié)構(gòu)定義如下：
{
long int number;
6、
struct Node *next;
}Node,*linkList;
#include //源程序：
#include
#include
#include
#define error 0
#define null 1
#define L sizeof(struct Node)
struct Node *create(int a)//鏈表創(chuàng)建函數(shù)
{
int n;
struct Node *p1, *p2, *head;
head = NULL;
7、 n = 0;
p2 = p1 = (struct Node *) malloc(L); //分配內(nèi)存
scanf("%ld", &p1->number);
while (a)//錄入鏈表信息
{
n = n + 1;
if (n == 1)
head = p1;
else
p2->next = p1;
p2 = p1;
p1 = (struct Node *) malloc(L);
if
8、(a != 1)//分配內(nèi)存
scanf("%ld", &p1->number);
a--; //控制輸入的個(gè)數(shù)
}
p2->next = NULL;
return (head);
}//鏈表創(chuàng)建函數(shù)結(jié)束
void print(struct Node *head)//輸出函數(shù)
{
struct Node *p;
p = head;
printf("數(shù)字:\n");
if (head != NULL)
do//循環(huán)實(shí)現(xiàn)輸出
{
9、 printf("%ld", p->number);
printf(" ");
p = p->next;
} while (p != NULL);
printf("\n");
}
//鏈表的交叉合并算法
struct Node * inter_link(struct Node * chain1, int a, struct Node * chain2, int b) {
int temp;
struct Node *head, *p1, *p2, *pos;
10、
/*判斷a，b大小并合并 */
if (a >= b) {
head = p1 = chain1;
p2 = chain2;
} else/*b>a*/ {
head = p1 = chain2;
p2 = chain1;
temp = a, a = b, b = temp; /*交換a和b*/
}
/*下面把p1的每個(gè)元素插在p2相應(yīng)元素之前，p1長a,p2長b*/
pos = head; /*此時(shí)pos指向p1中的第一個(gè)元素*/
w
11、hile (p2 != NULL) {//漂亮，蛇形插入
p1 = p1->next;
pos->next = p2;
pos = p2;
p2 = p2->next;
pos->next = p1;
pos = p1;
}
return head;
}
//對合并好的鏈表進(jìn)行排序
void InsertSort(struct Node *p, int m)//排序函數(shù)
{
int i, j, t;
struct Node *k;
12、 k = p;
for (i = 0; i < m - 1; i++) {
for (j = 0; j < m - i - 1; j++) {
if (p->number > (p->next)->number) {
t = p->number;
p->number = (p->next)->number;
(p->next)->number = t;
}
p = p->next;
13、 }
p = k;
}
}
struct Node * delete_link(struct Node *p,int i) //按位刪除
{ struct Node *q;
int j=0;
while(jnext)
{ p=p->next;
j++;
}
if(j==i-1&&p->next)
{
q=p->next;
p->next=q->next;
free(q);
}
else return erro
14、r;
}
struct Node * delete_linkz(struct Node *p,int i)//按值刪除
{ struct Node *q;
struct Node *k;
int j=0;
int h=0;
while(p&&p->number!=i)
p=p->next;
j++;
if (p)
{
while (hnext){
p=p->next;
h++;
}
if(h==j-1&&p->next){
k=p->next;
15、 p->next=k->next;
free(k);
}
}
else
return error;
}
//主函數(shù)
int main()//main函數(shù)
{
struct Node *p1, *p2;
int a;
int b;
int h;
int t;
int m;
printf("請輸入第一個(gè)鏈表:\n");
printf("\n輸入鏈表的長度a:\n");
scanf("%d", &a);
printf("請輸入鏈表數(shù)據(jù)：");
p1 = c
16、reate(a);
printf("\n你剛才輸入的第一個(gè)鏈表信息:\n ");
print(p1);
printf("\n 請輸入第二個(gè)鏈表:\n");
printf("\n輸入鏈表的長度b:\n");
scanf("%d", &b);
printf("請輸入鏈表數(shù)據(jù)：");
p2 = create(b);
printf("\n你剛才輸入的第二個(gè)鏈表的信息:\n");
print(p2);
p1 = inter_link(p1, a, p2, b);
h = a + b;
17、printf("\n合并后的鏈表\n：");
print(p1);
InsertSort(p1, h);
printf("\n排序后的鏈表:\n");
print(p1);
printf("\n請輸入鏈表中你所要?jiǎng)h除數(shù)據(jù)的所在位置:\n");
scanf("%d",&t);
delete_link(p1,t);
printf("\n鏈表刪除數(shù)據(jù)后鏈表的信息:\n");
print(p1);
printf("\n請輸入你想要?jiǎng)h除的數(shù)值:\n");
scanf("%d",&m);
delete_linkz(p1,m);
18、
printf("\n鏈表刪除數(shù)據(jù)后鏈表的信息:\n");
print(p1);
return 0;
}六．顯示結(jié)果
（1）mn
3.m=n
4.按位刪除操作
5.按值刪除
七．課程設(shè)計(jì)的總結(jié)
通過進(jìn)一周的學(xué)習(xí)和實(shí)踐，解決實(shí)際問題，讓我對鏈表有了更深的了解，也讓我提高了解決實(shí)際問題的能力。在上機(jī)的同時(shí)改正了自己對某些算法的錯(cuò)誤使用，使自己在通過程序解決問題時(shí)抓住關(guān)鍵算法，有了算法設(shè)計(jì)思想和流程圖，并用C語言描繪出關(guān)鍵算法。 在運(yùn)行過程中，用戶可輸入你所需合并的兩個(gè)鏈表，首先輸入你所要輸入鏈表的長度再
19、輸入鏈表的數(shù)據(jù)，完成第一個(gè)鏈表的輸入后，按照同樣的方法輸入第二個(gè)鏈表，每輸入完一個(gè)鏈表程序都會執(zhí)行輸出函數(shù)void print(struct Node *head)對鏈表進(jìn)行輸出，以此讓用戶可以確認(rèn)自己輸入的數(shù)據(jù)是否準(zhǔn)確。當(dāng)用戶輸入完第二個(gè)鏈表時(shí)，程序會先執(zhí)行struct Node * inter_link(struct Node * chain1, int a, struct Node * chain2, int b)再執(zhí)行void InsertSort(struct Node *p,int m)來進(jìn)行合并和排序。合并之后和排序后又分別會再次執(zhí)行輸出函數(shù)，以此輸出合并后和排序后的鏈表數(shù)據(jù)。之后相應(yīng)的按照用戶的需要可以刪除所要?jiǎng)h除的數(shù)據(jù)。
14
嚴(yán)選內(nèi)容#
鏈表的合并 實(shí)驗(yàn)報(bào)告#參考資料
