数据结构课程链表设计报告

华中科技大学文华学院数据结构课程设计课 程：数据结构题 目：链表操作专业班级：09软件工程（1）班 设计时间：2011指导教师：杨薇薇设计题目课程设计题四：链表操作1、设计目的 掌握线性链表的建立。 掌握线性链表的基本操作。2、设计内容和要求利用链表的插入运算建立线性链表，然后实现链表的查找、删除、 计数、输出、排序、逆置等运算，插入、删除、查找、计数、输出、 排序、逆置要单独写成函数，并能在屏幕上输出操作前后的结果。二、运行环境(软、硬件环境)硬件环境：普通PC机软件环境：VC6.0三、算法设计的思想选用单链表作为数据元素的存储结构，对每个数据元素，由一个数据域 和一个指针域组成，数据域放输入的数值，指针域指向下一个结点 数据结构单链表结点类型typedef struet LNodeElemType data;struet LNode *next;LinkList;模块划分void Ini tLis t(LinkLis t & L)/初始化int Lis tl nser t_ L(LinkLis t & L,i nt i,ElemType e)/插入元素 ElemType Lis tDele te_L(LinkLis t & L,i nt i)/删除元素 int Cou nt( LinkLis t L,ElemType e)/查找元素的位置 void Pri nt Lis t( LinkLis t L)/打印链表LinkLis t Sor tLis t(LinkLis t * L)/递增排序函数void ReverseOrder(LinkLis t & L)/求逆序void main()/主函数，分别调用以上的子函数功能设计首先利用元素插入法建立链表建立链表，然后导出菜单，用switch调用 各个子函数，实现链表的查找、删除、计数、输出、排序、逆置等运算, 其中元素插入用的是头插法，排序用的是冒泡法。四、算法的流程图主流程图:五、算法设计分析首先利用元素插入法建立链表建立链表，然后导出菜单，用switch调用各个子函 数，实现链表的查找、删除、计数、输出、排序、逆置等运算，其中元素插入用的 是头插法，排序用的是冒泡法，冒泡排序是稳定排序for(p=L;p!=NULL;p=p-next) for(q二p-next;q!二NULL;q=q-next)if(p-dataq-data)temp二qdata;q-data二p-data;pdata=temp;六、源代码#define NULL 0#include stdio.h #include malloc.h typedef int ElemType; typedef struct LNodeElemType data; struct LNode *next;LinkList;void InitList(LinkList &L)/初始化L.nex t=N ULL;int Lis tl nser t_ L(LinkLis t & L,i nt i,ElemType e)/插 入元素 LinkLis t *s,*p;p二&L;int j=0;while(p&ji-l)p=pnext;j+;if(!p|ji-l)return 0;s=(LinkList *)malloc(sizeof(LinkList);sdata二e;snext=p-next;p-next=s;return 1;ElemType Lis tDele te_L(LinkLis t & L,i nt i)/删除元素 LinkList *q,*p=&L;ElemType e;int j=0; while(p-next&ji-1)p=pnext; j+;if(!pnext&ji-1)return 0;q=pnext;pnext=qnext;e=q-data; free(q);return e; int Cou nt( LinkLis t L,ElemType e)/查找元素的位置 LinkList *p=L.next;int n=1;while(p)if(p-data=e)return n;n+; p=pnext;return 0;void ReverseOrder(LinkLis t & L)/求逆序 LinkLis t *pl,*s,*p二L.nex t; s=pnext;p-next=NULL; while(s-next)p1=snext; snext=p;p=s; s=p1;snext=p;L.nex t=s; void Prin tLis t(LinkLis t L)/打 印链表LinkList *p;p二L.nex t; while(p)pri ntf (%d ,p-da ta); p=pnext;printf(n)；int Lis tleng th(LinkList *L) /求链表长度LNode *p; /链表的单个元素指针，而不能用链表 int j=0;P=L; /将其指向链表的第一个元素 while(pnext!二NULL)+j;p=pnext;return j;LinkLis tSor tLis t(LinkLis t*L)/递增排序函数：入口参数：链表的头指针，此为链表中 的排序函数LinkList *p,*q; int temp;for(p二L;p!二NULL;p二p-next)for(q=p-next;q!二NULL;q=q-next) if(p-dataq-data)temp二qdata; q-data二p-data;pdata=temp;return *L; void main()LinkList HY;InitList(HY);int n,i=l;ElemType e=1,x;printf (请输入HY链表中的元素(按0结束)：n);while(e)scanf(%d，& e); if(!e)break;Lis tl nser t_ L(HY,i+,e);for(i=0;i20;i+)prin tf (* * );请输入以下数字执行相应程序：1：向链表中插入元素2:删除链表中的某个元素printf(* );printf(* );printf(* );printf(*3:按值查找元素的位置* );printf(*4:统计链表中元素个数* );printf(*5:输出链表* );printf(*6:将链表中元素按升序排列* );printf(*7:求链表的逆序* );for(i=0;i20;i+)prin tf (* * );int keyL;label: printf (请输入数字执行相应程序，按0结束程序！ n); scanf(%d，&keyL);if(!keyL)goto end;switch(keyL)case 1:printf(请输入在HY链表中要插入的位置和数(用空格隔开)：n); scanf(%d %d, &i, &e);Lis tl nser t_ L(HY,i,e);break;case 2:printf (请输入删除HY链表中第几个元素：n); scanf(%d，&n);x=Lis tDele te_L(HY,n);printf(删除了第d 个元素%dn,n,x);break;case 3:printf(请输入一个数，查找它的位置：n); scanf(%d，& e);if(Coun t( HY,e)printf (找到它的位置：第%d 个n,Count(HY,e);break;case 4:printf(该链表的元素个数为：%dn,Listlength(&HY);break;case 5:printf(当前链表的元素如下：n);PrintList(HY);break;case 6:printf(按升序排序后的链表如下：n);SortList(&HY);PrintList(HY);break;case 7:printf(当前链表的逆序如下：n);ReverseOrder(HY);PrintList(HY);break;default:printf（输入错误! n）; goto label;goto label;end: printf（程序结束！ n）;七、运行结果分析向链表中插入元素，把18插入到第二个位置:删除第4个元素7-In74个元素734C：c *G:ra表搽作DebugfiS表掾件驱匕统计链表中元素个: 输出链表请链表申元蕊按升序排列 求链表岛逆修尊输入数字执行相应程序，按/吉彙春;* 请输入在HY链表中要插入的位置和数（用空格隔开）：2 1召请输入数字执行相应程序，按磋吉東程序！当前链表的元素如下：1 18 274 98 23 5 12请输入数字执行相应程序，按0结束程序!请输入删除毗链表中第几个元素：4删请人数字执行相应程序，按磋吉東程序!当前链表的元素如下：1 18 2 4 98 23 5 i2请输入数字执行相应程序，按0结束程序!按值查找元素位置，找23：旗G八链表操件DebugfiJ表操eze021532894721升 # 按* 元逆* 1*下表表禽*序*以表链查链链表表程*入链除常出链链*束*炷嗚1 :2:3:4:5:6:7:# 知* * ,* *序* 程* 兴应* 行w W执* *字* 数* *|1 A* *输 * 请 3 请23找请第相1234567 *数插中元中程”应素:元幕 #Z.仃位个 ”执元聶素 二天的素元统计元素个数C：c弋：链表操ffDebugfiS表操件-eze02153284721 lx程”应素:元幕 * 位个 执元番素 二天的素元*数插中元中升* 按*J* 元逆 *下表表鬲* *以表链查链链表表捉 *入链除常出链链”请12 3 4 5 6 7 *链输te升序排列元素肚G八链表操ffDebugfiJ表操exe02153289472素元幕 二仃乗位个 ”执元番素 二天的素元数插中元中升 * 按* 元逆* *下表表禽* *以表链查链链表表* *入链除专出链链#请1234567 *二仃TH*-M-4e-M-4e-M-M-按升序排序后的链表如下：1 2 4 5 7 12 23 98请输入数字执行相应程序，按0结東程序!程应*相二仃位个执元番素 二天的素元求链表的逆序沁G八链表操作DebugfiJ表操ft- ese02153284 *7 *2 *1 歹 *一二申 * 序* 升 * 按* 元逆* !*下表表禽*序*以表链查链链表表*程*入链除常出链链*束*為価畫讓曲*瞄* 注嗚1 :2:3:4:5:6:7:*K0共 序程应*相 二仃*执*?:*数*入输*请素元幕*数插中元中123456? *序？行 艺4丸 阿98字 蔻3娄 连2入 苛5命 当12请八、收获及体会