C語言 雙向循環(huán)鏈表增刪查改判斷回文排序論文代碼

1、數(shù)學(xué)與計算機學(xué)院課程設(shè)計說明書課 程 名 稱: 數(shù)據(jù)結(jié)構(gòu)與算法A設(shè)計實踐 課 程 代 碼: 6015059 題 目 一: 線性表的鏈?zhǔn)奖硎竞蛯崿F(xiàn) 題 目 二: 利用棧實現(xiàn)表達式求解 年級/專業(yè)/班: 2011/信科/2班 學(xué) 生 姓 名: 彭丹 開 始 時 間: 2014 年 5 月 28 日完 成 時 間: 2014 年 6 月 28 日課程設(shè)計成績：學(xué)習(xí)態(tài)度及平時成績（30）技術(shù)水平與實際能力（20）創(chuàng)新（5）說明書撰寫質(zhì)量（45）總 分（100）指導(dǎo)教師簽名： 年 月 日目 錄摘要11 引言22 實驗一32.1整體設(shè)計思路32.2編碼32.3程序演示6摘 要 隨著計算機的普遍應(yīng)用與日益發(fā)

2、展，其應(yīng)用早已不局限于簡單的數(shù)值運算，數(shù)據(jù)結(jié)構(gòu)與算法的學(xué)習(xí)就是為以后利用計算機資源高效地開發(fā)非數(shù)值處理的計算機程序打下堅實的理論、方法和技術(shù)基礎(chǔ)。數(shù)據(jù)結(jié)構(gòu)與算法旨在分析研究計算機加工的數(shù)據(jù)對象的特性，以便選擇適當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)和存儲結(jié)構(gòu)，從而使建立在其上的解決問題的算法達到最優(yōu)。 本次數(shù)據(jù)結(jié)構(gòu)實踐的第一個實驗是線性表的鏈?zhǔn)奖硎竞蛯崿F(xiàn)，要求動態(tài)地建立循環(huán)鏈表并實現(xiàn)循環(huán)鏈元素的插入，刪除，查詢；使用雙向鏈的結(jié)構(gòu)實現(xiàn)判斷一個錄入的字符串是否是回文；建立一個單向鏈表，實現(xiàn)其內(nèi)元素非遞減排序。 關(guān)鍵詞：數(shù)據(jù)結(jié)構(gòu)與算法 線性表 鏈?zhǔn)浇Y(jié)構(gòu) 棧 表達式求解1 引 言 1. 1問題的提出 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計是重要地實

3、踐性教學(xué)環(huán)節(jié)。在進行了程序設(shè)計語言課和 數(shù)據(jù)結(jié)構(gòu)與算法課程教學(xué)的基礎(chǔ)上，設(shè)計實現(xiàn)相關(guān)的數(shù)據(jù)結(jié)構(gòu)經(jīng)典問題，有助于加深對數(shù)據(jù)結(jié)構(gòu)課程的認識。本課程設(shè)計是數(shù)據(jù)結(jié)構(gòu)中的一個關(guān)于線性表鏈?zhǔn)奖硎镜膶崿F(xiàn)還有用棧實現(xiàn)表達式求解，此課程設(shè)計要求對棧存儲結(jié)構(gòu)和鏈表存儲結(jié)構(gòu)非常熟悉，并能熟練使用它們。1.2 C語言 C語言既有高級語言的特點，又具有匯編語言的特點；既是一個成功的系統(tǒng)設(shè)計語言，有時一個使用的程序設(shè)計語言；既能用來編寫不依賴計算機硬件的應(yīng)用程序，又能用來編寫各種系統(tǒng)程序；是一種受歡迎、應(yīng)用廣泛的程序設(shè)計語言。1.3 C語言發(fā)展過程1973年，美國貝爾實驗室的D.M.RITCHIE在B語言的基礎(chǔ)上最終設(shè)計

4、出了一種新的語言，他取了BCPL的第二個字母作為這種語言的名字，這就是C語言。1977年Dennis M.Ritchie 發(fā)表了不依賴于具體機器系統(tǒng)的C語言編譯文本可移植的C語言編譯程序。1978年Brian W.Kernighian和Dennis M.Ritchie出版了名著The C Programming Language，從而使C語言成為目前世界上流行最廣泛的高級程序設(shè)計語言。1.4任務(wù)題目一：線性表的鏈?zhǔn)奖硎竞蛯崿F(xiàn) 第一個實驗主要是實現(xiàn)一些線性表的基本操作。包括（1）動態(tài)地建立循環(huán)鏈表；（2）實現(xiàn)循環(huán)鏈元素的插入，刪除，查詢；（3）使用雙向鏈的結(jié)構(gòu)實現(xiàn)判斷一個錄入的字符串是否是回文；

5、（4）建立一個單向鏈表，實現(xiàn)其內(nèi)元素非遞減排序。2 實驗一 線性表的鏈?zhǔn)奖硎竞蛯崿F(xiàn)2. 1整體設(shè)計思路1、實現(xiàn)循環(huán)鏈表建立要定義鏈表的節(jié)點，一個節(jié)點至少應(yīng)該包含數(shù)據(jù)域（data），指針域（point）兩個部分，動態(tài)建立循環(huán)鏈表的過程實際上就是生成節(jié)點并且將節(jié)點一個個相連接的過程。2、鏈元素的增刪查；增加節(jié)點既在指定的序號處添加節(jié)點的操作；刪除既從鏈表中取掉某個節(jié)點；查詢既匹配某個值，返回節(jié)點位置的操作。3、回文是從首到尾讀自負與從尾到首讀取字符都一樣的字符串，我們將字符串的每個字符分別存入一個節(jié)點中，飯后將節(jié)點連接起來就構(gòu)成了一個字符串鏈表。我們?nèi)〉谝粋€和最后一個節(jié)點，然后比較他們的值（dat

6、a）是否相等，若相等則取第二個和倒數(shù)第二個比較以此類推直到娶到最中間的字符為止，由此便可判斷出字符串是否回文。4、排序：由于要遞增排序，我們先在被排序的鏈表中選出最小的值得節(jié)點，然后將節(jié)點從鏈表中移除，再將這個節(jié)點添加到一個新建的鏈表，然后以此選擇最小值添加到該鏈表的末尾，當(dāng)原鏈表不含任何元素時，新鏈表即為排好序的鏈表。 2.2 編碼：創(chuàng)建節(jié)點：status creatNode ( node *no, elemtype elem )/創(chuàng)建節(jié)點 *no = (node *)malloc ( sizeof (node) ); (*no)->data = elem; (*no)->fpo

7、int = *no;/*head 表示head指針實際指向的地址 (*no)->lpoint = *no; if ( no = NULL ) exit ( overflow ); return ok;增加節(jié)點：status addNode ( node *head, int i, node *beAdd )/增加節(jié)點 if ( *head = NULL ) *head = beAdd; return ok; node *p = *head; int count = countNode ( p ); if ( i > countNode ( p ) | i = 0 )/當(dāng)i>c

8、ount時 在末尾添加，且規(guī)定當(dāng)i=0時在末尾添加 beAdd->lpoint = p; beAdd->fpoint = p->fpoint; beAdd->fpoint->lpoint = beAdd; p->fpoint = beAdd; return ok; else if ( i = 1 )/當(dāng)i=1的時候 beAdd->lpoint = p; beAdd->fpoint = p->fpoint; beAdd->fpoint->lpoint = beAdd; p->fpoint = beAdd; p = p->

9、;fpoint; *head = p; return ok; else/當(dāng)1<i<count時候 int j = 1; while ( j < i ) j+; p = p->lpoint; beAdd->lpoint = p; beAdd->fpoint = p->fpoint; beAdd->fpoint->lpoint = beAdd; p->fpoint = beAdd; return ok; 刪除節(jié)點：status deleteNode ( node *head, int i )/刪除節(jié)點 if ( countNode ( *

10、head ) < 1 | countNode ( *head ) < i ) printf ( "鏈表head中不包含第 %d 個節(jié)點n", i ); return error; node *p = *head; int j = 1; while ( j < i ) j+; p = p->lpoint; p->fpoint->lpoint = p->lpoint; p->lpoint->fpoint = p->fpoint; if ( i = 1 ) if ( *head = (*head)->lpoint

11、) (*head) = NULL; else *head = (*head)->lpoint; free ( p ); return ok;查詢節(jié)點：int findNode ( node *head, elemtype elem )/根據(jù)值找到節(jié)點 int pos = 0; node *p = head; pos+; if ( p = NULL ) return 0; else if ( p->data = elem ) return pos; while ( p != NULL&&p->lpoint != head ) p = p->lpoint;

12、pos+; if ( p->data = elem ) return pos; break; return 0;判斷回文：bool isPalin ( node *head )/判斷回文 bool flag = true;/標(biāo)志量 true表示是回文 node *p = head; node*p1 = p->fpoint; int i = countNode ( head ) / 2; int j = 1; while ( j <= i ) if ( p->data != p1->data ) flag = false; break; j+; return fla

13、g;鏈表排序：status sortList ( node *head )/ 排序 int minPos;/最小節(jié)點的位置 node *h = *head; node *newHead = NULL;/新建的鏈表 node *temp = NULL; while ( countNode ( h ) != 0 )/當(dāng)原鏈表不為空 removeNode ( &h, findNode ( h, findMin ( h ) ), &temp );/將找到的最小節(jié)點從原鏈表中移除，并放入temp節(jié)點中 addNode ( &newHead, 0, temp );/將temp節(jié)點插

14、入新鏈表的末尾 temp = NULL; *head = newHead; return ok;2.3 程序演示：程序開始：輸入2 選擇增、刪、查項。插入一個節(jié)點在第二個節(jié)點前，值為203：插入前后對比：查詢節(jié)點值 100：以上鏈表排序前后對比：刪除第3個節(jié)點：判斷回文：結(jié) 論 這一次的課程設(shè)計相比之前的幾次算是比較簡單和輕松的了，但是還是會有很多問題出現(xiàn)，主要問題體現(xiàn)在對C語言的遺忘，有些東西不記得了，需要看以前的學(xué)習(xí)的書再次鞏固一下。本次實踐做了兩個題，一個是線性表的鏈?zhǔn)奖硎竞蛯崿F(xiàn)，另一個是利用棧實現(xiàn)表達式求解。在做線性表的時候?qū)χ羔樀氖褂眠€不是很好，容易出錯，在同學(xué)及老師的幫助下，順利解

15、決。在做利用棧實現(xiàn)表達式求解問題的時候，對棧的理解必須到位才可以做好，特別是表達式求解時什么時候進棧什么時候出棧是很重要的，匹配括號是其中一個難點。經(jīng)過本次課程設(shè)計，相當(dāng)于復(fù)習(xí)了C語言和數(shù)據(jù)結(jié)構(gòu)，也鍛煉了程序設(shè)計的能力，收獲頗多。參考文獻1譚浩強 等.C語言程序設(shè)計教程.高等教育出版社.20052李建學(xué) 等.數(shù)據(jù)結(jié)構(gòu)課程設(shè)計案例精編（用C/C+描述）.清華大學(xué)出版.2007-2-13嚴蔚敏 等.數(shù)據(jù)結(jié)構(gòu)(C語言版).清華大學(xué)出版社.2003-1附錄：Cpp1：函數(shù)部分#include "stdafx.h"#include<stdio.h>#include <

16、;string.h>#include <conio.h>#include <stdlib.h>#include<ctype.h>using namespace System;#define false 0#define true 1#define error -1#define ok 1#define overflow -2typedef int status;typedef int elemtype;typedef struct node elemtype data; struct node *fpoint; struct node * lpoint

17、;node; /結(jié)構(gòu)體類型nodestatus creatList ( node *head )/創(chuàng)建鏈表/關(guān)于此處的*：當(dāng)我們寫：node*head 只是定義了一個指向node的指針，顯然，此處我們還要改寫這個指針head的值 ，所以我們需要指向該指針的指針node*p；父函數(shù)調(diào)用時傳遞一個head類型指針的地址即可：&head，否則會出現(xiàn)類型不匹配錯誤！ *head = (node *)malloc ( sizeof (node) ); (*head)->data = 100; (*head)->fpoint = *head;/*head 表示head指針實際指向的地址

18、！ (*head)->lpoint = *head; if ( head = NULL ) exit ( overflow ); return ok;status creatNode ( node *no, elemtype elem ) *no = (node *)malloc ( sizeof (node) ); (*no)->data = elem; (*no)->fpoint = *no;/ 前指針 (*no)->lpoint = *no;/后指針 if ( no = NULL ) exit ( overflow ); return ok;int countNo

19、de ( node *head )/計算節(jié)點數(shù) int cout; if ( head = NULL ) return 0; else cout+; node *h = head; while ( h->lpoint != head ) cout+; h = h->lpoint; return cout;status outList ( node *head ) printf ( "序號t節(jié)點值n" ); if ( head != NULL ) node *h = head; node *h1 = head; int i = 1; do printf ( &qu

20、ot;%4dt%6dn", i, h->data ); h = h->lpoint; i+; while ( h != head ) printf ( "%4dt%6d n", i, h->data ); i+; h = h->lpoint; break; while ( h != NULL ); return ok;status addNode ( node *head, int i, node *beAdd ) if ( *head = NULL ) *head = beAdd; return ok; node *p = *head;

21、int count = countNode ( p ); if ( i > countNode ( p ) | i = 0 ) beAdd->lpoint = p; beAdd->fpoint = p->fpoint; beAdd->fpoint->lpoint = beAdd; p->fpoint = beAdd; return ok; else if ( i = 1 ) beAdd->lpoint = p; beAdd->fpoint = p->fpoint; beAdd->fpoint->lpoint = beAdd

22、; p->fpoint = beAdd; p = p->fpoint; *head = p; return ok; else int j = 1; while ( j < i ) j+; p = p->lpoint; beAdd->lpoint = p; beAdd->fpoint = p->fpoint; beAdd->fpoint->lpoint = beAdd; p->fpoint = beAdd; return ok; status outNode ( node * head, int i ) return ok;status

23、 deleteNode ( node *head, int i ) if ( countNode ( *head ) < 1 | countNode ( *head ) < i ) printf ( "鏈表head中不包含第 %d 個節(jié)點n", i ); return error; node *p = *head; int j = 1; while ( j < i ) j+; p = p->lpoint; p->fpoint->lpoint = p->lpoint; p->lpoint->fpoint = p->f

24、point; if ( i = 1 ) if ( *head = (*head)->lpoint ) (*head) = NULL; else *head = (*head)->lpoint; free ( p ); return ok;status removeNode ( node *head, int i, node *no ) if ( countNode ( *head ) < 1 | countNode ( *head ) < i ) printf ( "鏈表head中不包含第 %d 個節(jié)點n", i ); return error; n

25、ode *p = *head; int j = 1; while ( j < i ) j+; p = p->lpoint; p->fpoint->lpoint = p->lpoint; p->lpoint->fpoint = p->fpoint; if ( i = 1 ) if ( *head = (*head)->lpoint ) (*head) = NULL; else *head = (*head)->lpoint; p->fpoint = p; p->lpoint = p; *no = p; return ok;s

26、tatus freeList ( node *head ) return ok;int findMin ( node *head ) node *p = head; if ( p = NULL ) puts ( "鏈表為空！" ); return 0; int min = p->data; while ( p != NULL&&p->lpoint != head ) p = p->lpoint; if ( p->data<min ) min = p->data; return min;int findNode ( node

27、 *head, elemtype elem ) int pos = 0; node *p = head; pos+; if ( p = NULL ) return 0; else if ( p->data = elem ) return pos; while ( p != NULL&&p->lpoint != head ) p = p->lpoint; pos+; if ( p->data = elem ) return pos; break; return 0;status sortList ( node *head ) int minPos; nod

28、e *h = *head; node *newHead = NULL; node *temp = NULL; while ( countNode ( h ) != 0 ) removeNode ( &h, findNode ( h, findMin ( h ) ), &temp ); addNode ( &newHead, 0, temp ); temp = NULL; *head = newHead; return ok;bool isHuiWen ( node *head ) bool flag = true; node *p = head; node*p1 = p

29、->fpoint; int i = countNode ( head ) / 2; int j = 1; while ( j <= i ) if ( p->data != p1->data ) flag = false; break; j+; return flag;Cpp2：菜單部分：/ data_struct_design.cpp: 主項目文件。#include "stdafx.h"#include<stdio.h>#include <string.h>#include <conio.h>#include &l

30、t;stdlib.h>#include<ctype.h>using namespace System;#define false 0#define true 1#define error -1#define ok 1#define overflow -2typedef int status;typedef int elemtype;typedef struct node elemtype data; struct node *fpoint; struct node * lpoint;node; /結(jié)構(gòu)體類型nodestatus outList ( node *head );s

31、tatus outNode ( node * head, int i );status deleteNode ( node *head, int i );status freeList ( node *head );status sortList ( node *head );status creatList ( node *head );status creatNode ( node *no, elemtype elem );int countNode ( node *head );status addNode ( node *head, int i, node *beAdd );int f

32、indNode ( node *head, elemtype elem );status removeNode ( node *head, int i, node *no );int findMin ( node *head );bool isHuiWen ( node *head );void func1_2 ( );void menu ( ) system ( "cls" ); puts ( "第二題：線性表的鏈?zhǔn)奖硎竞蛯崿F(xiàn)2" ); puts ( "1 動態(tài)地建立循環(huán)鏈表；" ); puts ( "2 實現(xiàn)循環(huán)鏈元素的

33、插入，刪除，查詢；" ); puts ( "3 使用雙向鏈的結(jié)構(gòu)實現(xiàn)判斷一個錄入的字符串是否是回文。" ); puts ( "4 建立一個單向鏈表，實現(xiàn)其內(nèi)元素非遞減排序" ); puts ( "*" ); char a10; gets ( a ); switch ( a0 ) case '1': puts ( "1 動態(tài)地建立循環(huán)鏈表：" ); node *head; node *p; creatList ( &head ); creatNode ( &p, 21 );

34、addNode ( &head, 1, p ); creatNode ( &p, 302 ); addNode ( &head, 1, p ); creatNode ( &p, 3 ); addNode ( &head, 1, p ); creatNode ( &p, 45 ); addNode ( &head, 1, p ); creatNode ( &p, 57 ); addNode ( &head, 0, p ); outList ( head ); puts ( "任意鍵返回：" ); getc

35、he ( ); while ( countNode ( head ) != 0 ) deleteNode ( &head, countNode ( head ) ); menu ( ); break; case '2': func1_2 ( ); break; case '3': system ( "cls" ); char a100; puts ( "請輸入要判斷的字符串" ); gets ( a ); int i = 0; node *p = NULL; node *h = NULL; while ( ai !

36、= '0' ) creatNode ( &p, ai ); addNode ( &h, 0, p ); i+; if ( isHuiWen ( h ) ) puts ( "您輸入的字符串是回文！" ); else puts ( "您輸入的字符串不是回文！" ); puts ( "字符串的正反序?qū)Ρ龋簄正序t反序n" ); int j = 0; node *m = h; node *n = h->fpoint; while ( j < countNode ( h ) ) printf ( &q

37、uot;%4ct%4cn", m->data, n->data ); m = m->lpoint; n = n->fpoint; j+; bool f = isHuiWen ( h ); puts ( "任意鍵返回" ); getche ( ); menu ( ); ; break; case '4': puts ( "4 建立一個單向鏈表，實現(xiàn)其內(nèi)元素非遞減排序" ); node *head; node *p; creatList ( &head ); creatNode ( &p, 2

38、1 ); addNode ( &head, 1, p ); creatNode ( &p, 302 ); addNode ( &head, 1, p ); creatNode ( &p, 3 ); addNode ( &head, 1, p ); creatNode ( &p, 45 ); addNode ( &head, 1, p ); creatNode ( &p, 57 ); addNode ( &head, 0, p ); outList ( head ); sortList ( &head ); puts

39、 ( "排序后的鏈表：" ); outList ( head ); puts ( "任意鍵返回" ); getche ( ); while ( countNode ( head ) != 0 ) deleteNode ( &head, countNode ( head ) ); menu ( ); break; default: menu ( ); puts ( "輸入不正確，請重新輸入：" ); void func1_2 ( ) system ( "cls" ); puts ( "2 實現(xiàn)循環(huán)鏈

40、元素的插入，刪除，查詢:" ); node *head; node *p; creatList ( &head ); creatNode ( &p, 21 ); addNode ( &head, 1, p ); creatNode ( &p, 302 ); addNode ( &head, 1, p ); creatNode ( &p, 3 ); addNode ( &head, 1, p ); creatNode ( &p, 45 ); addNode ( &head, 1, p ); creatNode ( &p, 57 ); addNode ( &head, 0, p ); outList ( head ); puts ( "*" ); puts ( "1 插入一個節(jié)點" ); puts ( "2 刪除一個節(jié)點" ); puts ( "3 查詢節(jié)點" ); puts ( "0 返回" )