《C语言 双向循环链表、增删查改、判断回文、排序、论文+代码》由会员分享，可在线阅读，更多相关《C语言 双向循环链表、增删查改、判断回文、排序、论文+代码（25页珍藏版）》请在金锄头文库上搜索。
1、 线性表及栈数学与计算机学院课程设计说明书课 程 名 称: 数据结构与算法A设计实践 课 程 代 码: 6015059 题 目 一: 线性表的链式表示和实现 题 目 二: 利用栈实现表达式求解 年级/专业/班: 2011/信科/2班 学 生 姓 名: 彭丹 学 号: 312011070102205 开 始 时 间: 2014 年 5 月 28 日完 成 时 间: 2014 年 6 月 28 日课程设计成绩：学习态度及平时成绩（30）技术水平与实际能力（20）创新（5）说明书撰写质量（45）总 分（100）指导教师签名： 年 月 日目 录摘要11 引言22 实验一32.1整体设计思路32.2编码
2、32.3程序演示6摘 要 随着计算机的普遍应用与日益发展，其应用早已不局限于简单的数值运算，数据结构与算法的学习就是为以后利用计算机资源高效地开发非数值处理的计算机程序打下坚实的理论、方法和技术基础。数据结构与算法旨在分析研究计算机加工的数据对象的特性，以便选择适当的数据结构和存储结构，从而使建立在其上的解决问题的算法达到最优。 本次数据结构实践的第一个实验是线性表的链式表示和实现，要求动态地建立循环链表并实现循环链元素的插入，删除，查询；使用双向链的结构实现判断一个录入的字符串是否是回文；建立一个单向链表，实现其内元素非递减排序。 关键词：数据结构与算法 线性表 链式结构 栈 表达式求解1
3、引 言 1. 1问题的提出 数据结构课程设计是重要地实践性教学环节。在进行了程序设计语言课和 数据结构与算法课程教学的基础上，设计实现相关的数据结构经典问题，有助于加深对数据结构课程的认识。本课程设计是数据结构中的一个关于线性表链式表示的实现还有用栈实现表达式求解，此课程设计要求对栈存储结构和链表存储结构非常熟悉，并能熟练使用它们。1.2 C语言 C语言既有高级语言的特点，又具有汇编语言的特点；既是一个成功的系统设计语言，有时一个使用的程序设计语言；既能用来编写不依赖计算机硬件的应用程序，又能用来编写各种系统程序；是一种受欢迎、应用广泛的程序设计语言。1.3 C语言发展过程1973年，美国贝尔
4、实验室的D.M.RITCHIE在B语言的基础上最终设计出了一种新的语言，他取了BCPL的第二个字母作为这种语言的名字，这就是C语言。1977年Dennis M.Ritchie 发表了不依赖于具体机器系统的C语言编译文本可移植的C语言编译程序。1978年Brian W.Kernighian和Dennis M.Ritchie出版了名著The C Programming Language，从而使C语言成为目前世界上流行最广泛的高级程序设计语言。1.4任务题目一：线性表的链式表示和实现 第一个实验主要是实现一些线性表的基本操作。包括（1）动态地建立循环链表；（2）实现循环链元素的插入，删除，查询；（3
5、）使用双向链的结构实现判断一个录入的字符串是否是回文；（4）建立一个单向链表，实现其内元素非递减排序。2 实验一 线性表的链式表示和实现2. 1整体设计思路1、实现循环链表建立要定义链表的节点，一个节点至少应该包含数据域（data），指针域（point）两个部分，动态建立循环链表的过程实际上就是生成节点并且将节点一个个相连接的过程。2、链元素的增删查；增加节点既在指定的序号处添加节点的操作；删除既从链表中取掉某个节点；查询既匹配某个值，返回节点位置的操作。3、回文是从首到尾读自负与从尾到首读取字符都一样的字符串，我们将字符串的每个字符分别存入一个节点中，饭后将节点连接起来就构成了一个字符串链表
6、。我们取第一个和最后一个节点，然后比较他们的值（data）是否相等，若相等则取第二个和倒数第二个比较以此类推直到娶到最中间的字符为止，由此便可判断出字符串是否回文。4、排序：由于要递增排序，我们先在被排序的链表中选出最小的值得节点，然后将节点从链表中移除，再将这个节点添加到一个新建的链表，然后以此选择最小值添加到该链表的末尾，当原链表不含任何元素时，新链表即为排好序的链表。 2.2 编码：创建节点：status creatNode ( node *no, elemtype elem )/创建节点 *no = (node *)malloc ( sizeof (node) ); (*no)-dat
7、a = elem; (*no)-fpoint = *no;/*head 表示head指针实际指向的地址 (*no)-lpoint = *no; if ( no = NULL ) exit ( overflow ); return ok;增加节点：status addNode ( node *head, int i, node *beAdd )/增加节点 if ( *head = NULL ) *head = beAdd; return ok; node *p = *head; int count = countNode ( p ); if ( i countNode ( p ) | i = 0
8、 )/当icount时 在末尾添加，且规定当i=0时在末尾添加 beAdd-lpoint = p; beAdd-fpoint = p-fpoint; beAdd-fpoint-lpoint = beAdd; p-fpoint = beAdd; return ok; else if ( i = 1 )/当i=1的时候 beAdd-lpoint = p; beAdd-fpoint = p-fpoint; beAdd-fpoint-lpoint = beAdd; p-fpoint = beAdd; p = p-fpoint; *head = p; return ok; else/当1icount时候
9、 int j = 1; while ( j lpoint; beAdd-lpoint = p; beAdd-fpoint = p-fpoint; beAdd-fpoint-lpoint = beAdd; p-fpoint = beAdd; return ok; 删除节点：status deleteNode ( node *head, int i )/删除节点 if ( countNode ( *head ) 1 | countNode ( *head ) i ) printf ( 链表head中不包含第 %d 个节点n, i ); return error; node *p = *head;
10、int j = 1; while ( j lpoint; p-fpoint-lpoint = p-lpoint; p-lpoint-fpoint = p-fpoint; if ( i = 1 ) if ( *head = (*head)-lpoint ) (*head) = NULL; else *head = (*head)-lpoint; free ( p ); return ok;查询节点：int findNode ( node *head, elemtype elem )/根据值找到节点 int pos = 0; node *p = head; pos+; if ( p = NULL
11、) 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;判断回文：bool isPalin ( node *head )/判断回文 bool flag = true;/标志量 true表示是回文 node *p = head; node*p1 = p-fpoint; int i = countNode ( head ) / 2; int j = 1; while ( j data != p1-data ) flag = false; break; j+; return flag;链表排序：status sortList ( node *head )/ 排序 int minPos;/最小节点的位置 node *h = *head;
