双向链表 非双向循环链表 完美实现 C语言 C++语言
#include < malloc.h >
#include < stdlib.h >
#include < iostream >
using namespace std;
#define OK 1
#define ERROR 0
#define NULL 0
/*-------双向链表的存储结构-------*/
typedef int ElemType;
typedef int Status;
typedef struct DuLNode{
ElemType data;
struct DuLNode *prior;
struct DuLNode *next;
} DuLNode,*DuLinkList;
/*-------双向链表涉及的函数-------*/
void InitList_DuL ( DuLinkList * L) ;//初始化一个链表
DuLinkList GetElemP_DuL ( DuLinkList * L,int n );
void ListInsert_DuL ( DuLinkList * L,int i,ElemType e);//双链表插入函数Status ListDelete_DuL ( DuLinkList * L,int i );//双链表删除某个结点ElemType GetLeadNode_DuL ( DuLinkList * L );
int GetLength_DuL ( DuLinkList * L );//获得双链表的长度
Status DestroyList_DuL ( DuLinkList * L );
void Traverse_DuL ( DuLinkList * L );
void InitList_DuL ( DuLinkList * L )
{ //初始化一个双链表,输入n个元素的值,建立带头结点的双链表* L if ( ! ( * L = ( DuLinkList ) malloc ( sizeof ( DuLNode ) ) ) )
{
cout< exit ( 0 ); } ( * L ) -> next = NULL; ( * L ) -> prior = NULL; int i = 1; DuLinkList current,first,s; ElemType e; cout<<"Input data,integer only,end with 0:"< cin>>e; while ( e ) { if ( ( s = ( DuLinkList ) malloc ( sizeof ( DuLNode ) ) ) == NULL ) { cout<<"An error occurred when malloc a new node"< exit ( 0 ); } if ( i == 1 ) //第一个结点的创建 { first = s; first -> data = e; first -> next = NULL; first -> prior = NULL; current = first; } else //其它结点的创建 { s -> data = e; s -> next = NULL; current -> next = s; s -> prior = current; current = s; } i++; cin>>e; } ( * L ) -> data = NULL; ( * L ) -> next = first;//使头结点指向第一个结点 ( * L ) -> prior = current;//这句话为什么可以省去? } DuLinkList GetElemP_DuL ( DuLinkList * L,int n ) { DuLinkList p = * L; int i = 0; while ( p && i < n - 1 ) { p = p -> next; i++; } if ( ! p || i > n - 1 ) { cout<<"Input position error!"< exit ( ERROR ); } return p; } void ListInsert_DuL ( DuLinkList * L,int i,ElemType e)//双链表插入函数 { DuLinkList current,New_node; New_node = ( DuLinkList ) malloc ( sizeof ( DuLNode ) ); New_node -> data = e; New_node -> prior = New_node -> next = NULL; current = GetElemP_DuL ( & ( * L ),i ); if ( ! ( current -> next ) ) { //如果是在末尾插入结点 New_node -> prior = current;//尾结点的前驱指向当前结点 current -> next = New_node;//新结点作为新的尾结点 } else //如果不是在末尾插入结点 { New_node -> next = current -> next;//当前结点的后继作为新结点的后继 current -> next -> prior = New_node;//当前结点后继的前驱指向新结点 current -> next = New_node;//将新结点作为当前结点的后继 New_node -> prior = current;//当前结点作为新结点的前驱 } } ElemType GetLeadNode_DuL ( DuLinkList * L )//获得首结点 { DuLinkList p = ( * L ) -> next; //因为第一个结点用来存链表长度了,所以要用->next return p -> data; } Status ListDelete_DuL ( DuLinkList * L,int i ) //双链表删除某个结点 { DuLinkList current; if ( ! ( current = GetElemP_DuL ( & ( * L ),i + 1 ) ) ) return ERROR; if ( ! ( current -> prior ) ) //如果是第一个结点 { ( * L ) -> next = current -> next;//头结点指向第二个结点 current -> next -> prior = NULL;//置空第二个结点(新的首结点)的前驱指针} else if ( ! ( current -> next ) ) //如果是删除尾结点 { current -> prior -> next = NULL; current -> prior = NULL; } else //不是第一个结点 { current -> prior -> next = current -> next;//当前结点前驱的后继指向当前结点的后继 current -> next ->prior = current -> prior;//当前结点的后继的前驱指向当前结点的前驱 } free ( current ); return OK; } int GetLength_DuL ( DuLinkList * L ) { int count = 0; if ( ! ( * L ) ); else { DuLinkList p = * L; while ( p ) { p = p -> next; ++count; } } return count; } Status DestroyList_DuL ( DuLinkList * L ) {//从头结点开始一一释放结点空间 DuLinkList p = * L,current; if ( !p ) { cout<<"No list to be destroyed!"< return ERROR; } while ( p ) //将结点的数据域和指针与全部置空,然后释放空间{ current = p; p = p -> next; free ( current ); } free ( p ); return OK; } void Traverse_DuL ( DuLinkList L ) { DuLinkList p = L -> next; while ( p ) { cout<<" <-"<< ( p -> data ) <<"-> "; p = p -> next; } cout< } int main() { DuLinkList L = NULL; InitList_DuL ( & L ); cout<<"ListInsert_DuL ( & L,3,8 )"< ListInsert_DuL ( & L,3,8 ); cout<<"ListDelete_DuL ( & L,1 )"< ListDelete_DuL ( & L,1 ); cout<<"首结点"< cout<<"length:"< Traverse_DuL ( L ); cout<<"DestroyList_DuL ( & L )"< DestroyList_DuL( & L ); cout<<"Destroy finished."< return 0; } #include Search(L); break; } case 5:{ Delete(&L); break; } case 6:{ bubblesort(&L); break; } case 7:{ selectsort(&L); break; } default :{ printf("\nOption is useless.Please input again."); break; } } if(flag){ printf("\nPlease pick an option: "); scanf("%d",&k); } } return 0; } void Input(SeqList *L){ int i,n; printf("Please input the sum of elements:\n"); scanf("%d",&n); while(n>MaxSize){ printf("Sum is bigger than MaxSize,please input again\n"); scanf("%d",&n); } printf("Input the elements of list:\n"); for(i=0;i 《数据结构与算法》期末复习题 一、选择题。 1．在数据结构中，从逻辑上可以把数据结构分为 C 。 A．动态结构和静态结构B．紧凑结构和非紧凑结构 C．线性结构和非线性结构D．内部结构和外部结构 2．数据结构在计算机内存中的表示是指 A 。 A．数据的存储结构B．数据结构C．数据的逻辑结构D．数据元素之间的关系 3．在数据结构中，与所使用的计算机无关的是数据的 A 结构。 A．逻辑B．存储C．逻辑和存储D．物理 4．在存储数据时，通常不仅要存储各数据元素的值，而且还要存储 C 。 A．数据的处理方法B．数据元素的类型 C．数据元素之间的关系D．数据的存储方法 5．在决定选取何种存储结构时，一般不考虑 A 。 A．各结点的值如何B．结点个数的多少 C．对数据有哪些运算D．所用的编程语言实现这种结构是否方便。 6．以下说法正确的是 D 。 A．数据项是数据的基本单位 B．数据元素是数据的最小单位 C．数据结构是带结构的数据项的集合 D．一些表面上很不相同的数据可以有相同的逻辑结构 7．算法分析的目的是 C ，算法分析的两个主要方面是 A 。 （1）A．找出数据结构的合理性B．研究算法中的输入和输出的关系C．分析算法的效率以求改进C．分析算法的易读性和文档性 （2）A．空间复杂度和时间复杂度B．正确性和简明性 C．可读性和文档性D．数据复杂性和程序复杂性 8．下面程序段的时间复杂度是O(n2) 。 s =0; for( I =0; i 《数据结构(C语言版)》复习重点 重点在二、三、六、七、九、十章，考试内容两大类：概念，算法 第1章、绪论 1. 数据：是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。 2. 数据元素：是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 3. 数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。 其4类基本结构：集合、线性结构、树形结构、图状结构或网状结构 4. 逻辑结构：是数据元素之间的逻辑关系的描述。 5. 物理结构（存储结构）：是数据结构在计算机中的表示（又称映像）。 其4种存储结构：顺序存数结构、链式存数结构、索引存数结构、散列存数结构6. 算法：是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。 其5个重要特性：有穷性、确定性、可行性、输入、输出 7. 时间复杂度：算法中基本操作重复执行的次数是问题规模n的某个函数f(n),算法的时间度量记作，T(n)=O(f(n))；他表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称做算法的渐进时间复杂度，简称时间复杂度。例如： (a) {++x;s=0;} (b) for(i=1;i<=n;++i){++x;s += x;} (c) for(j=1;j<=n;++j) for(k=1;k<=n;++k){++x;s += x;} 含基本操作“x增1”的语句的频度分别为1、n和n2，则这3个程序段的时间复杂度分别为O(1)、O(n)和O(n2)，分别称为常量阶、线性阶和平方阶。还可呈现对数阶O(log n)、指数阶O(2的n次方)等。 8. 空间复杂度：算法所需存储空间的度量记作，S(n)=O(f(n))。 第2章、线性表 1. 线性表：是最常用最简单的一种数据结构，一个线性表是n个数据元素的有限序列。 2. 线性表的顺序存储结构：是用一组地址连续的存储单元依次存储线性表的数据元素。其特点为逻辑关系上相邻的两个元素在物理位置上也相邻，可以随机存取表中任一元素。 存储位置计算：假设线性表的每个元素需占用L个存储单元，并以所占的第一个单元的存储地址作为数据元素的存储位置，线性表的第i个数据元素ai的存储位置为LOC(ai)=LOC(a1)+(i-1)*L 式中LOC(a1)是线性表第一个元素a1的存储位置，通常称做线性表的起始位置或基地址。 3. 线性表的链式存储结构：是用一组任意的存储单元存储线性表的数据元素(这组存储单元可以是连续的，也可以是不连续的)。 数据结构（C语言版）期末复习汇总 第一章绪论 数据结构：是一门研究非数值计算程序设计中的操作对象，以及这些对象之间的关系和操作的学科。 数据结构是一门综合性的专业课程，是一门介于数学、计算机硬件、计算机软件之间的一门核心课程。是设计和实现编译系统、操作系统、数据库系统及其他系统程序和大型应用程序的基础。 数据：是客观事物的符号表示，是所有能输入到计算机中并被计算机程序处理的符号的总称。 如数学计算中用到的整数和实数，文本编辑中用到的字符串，多媒体程序处理的图形、图像、声音及动画等通过特殊编码定义后的数据。 数据的逻辑结构划分：线、树、图 算法的定义及特性 算法：是为了解决某类问题而规定的一个有限长的操作序列。 五个特性：有穷性、确定性、可行性、输入、输出 评价算法优劣的基本标准（4个）： 正确性、可读性、健壮性、高效性及低存储量 第二章线性表 线性表的定义和特点： 线性表：由n(n≥0)个数据特性相同的元素构成的有限序列。线性表中元素个数n(n≥0)定义为线性表的长度，n=0时称为空表。 非空线性表或线性结构，其特点： （1）存在唯一的一个被称作“第一个”的数据元素； （2）存在唯一的一个被称作“最有一个”的数据元素； （3）除第一个之外，结构中的每个数据元素均只有一个前驱； （4）除最后一个之外，结构中的每个数据元素均只有一个后继。 顺序表的插入：n个元素在i位插入，应移动（n-i+1）位元素。 顺序表存储结构的优缺点： 优点： 逻辑相邻，物理相邻；可随机存取任一元素；存储空间使用紧凑； 缺点： 插入、删除操作需要移动大量的元素；预先分配空间需按最大空间分配，利用不充分； 表容量难以扩充； 线性表的应用： 一般线性表的合并：★★★ 算法2.1：LA=(7,5,3,11) LB=(2,6,3) 合并后LA=(7,5,3,11,2,6) 算法思想：扩大线性表LA，将存在于线性表LB中而不存在于线性表LA中的数据元素插入到线性表LA中去。只要从线性表LB中依次取得每个数据元素，并依值在线性表LA中 详解堆栈的几种实现方法——C语言版 基本的抽象数据类型（ADT）是编写C程序必要的过程，这类ADT有链表、堆栈、队列和树等，本文主要讲解下堆栈的几种实现方法以及他们的优缺点。 堆栈（stack）的显著特点是后进先出（Last-In First-Out, LIFO），其实现的方法有三种可选方案：静态数组、动态分配的数组、动态分配的链式结构。 静态数组：特点是要求结构的长度固定，而且长度在编译时候就得确定。其优点是结构简单，实现起来方便而不容易出错。而缺点就是不够灵活以及固定长度不容易控制，适用于知道明确长度的场合。 动态数组：特点是长度可以在运行时候才确定以及可以更改原来数组的长度。优点是灵活，缺点是由此会增加程序的复杂性。 链式结构：特点是无长度上线，需要的时候再申请分配内存空间，可最大程度上实现灵活性。缺点是链式结构的链接字段需要消耗一定的内存，在链式结构中访问一个特定元素的效率不如数组。 首先先确定一个堆栈接口的头文件，里面包含了各个方案下的函数原型，放在一起是为了实现程序的模块化以及便于修改。然后再接着分别介绍各个方案的具体实施方法。 堆栈接口stack.h文件代码： [cpp]view plaincopy 1./* 2.** 堆栈模块的接口 stack.h 3.*/ 4.#include //C语言课程设计职工信息管理系统—单链表实现 #include "stdio.h" #include "stdlib.h" #include "string.h" int saveflag=0; /*是否需要存盘的标志变量*/ struct employee { char name[15]; char num[10];/* 工号 */ char sex[4]; char bm[15]; char zc[20]; int gz; }; typedef struct node { struct employee data; struct node *next; }Node,*Link; //Link l (注意是：字母l不是数字1) void add(Link l); void disp(Link l); //查看职工所有信息 void del(Link l); //删除功能 Node* Locate(Link l,char findmess[],char nameornum[]); void Qur(Link l); //查询功能 void Tongji(Link l); //统计 void Sort(Link l); //排序 void Modify(Link l); //修改功能 void save(Link l); //将单链表l中的数据写入文件 void printe(Node *p); //本函数用于打印链表中某个节点的数据内容 */ //以下4个函数用于输出中文标题 void printstart(); void Wrong(); void Nofind(); void printc(); 数据结构(C语言版)例题（第三章：栈和队列） (2008-05-09 12:33:13) 转载▼ ◆3.15③假设以顺序存储结构实现一个双向栈，即在一维数组的存储空间中存在着两个栈，它们的栈底分别设在数组的的两个端点。 试编写实现这个双向栈tws的三个操作:初始化inistack(tws)、入栈 push(tws,i,x)和出栈pop(tws,i,x)的算法, 其中i为0或1，用以分 别指示设在数组两端的两个栈，并讨论按过程（正/误状态变量可设 为变参）或函数设计这些操作算法各有什么优缺点。 实现下列3个函数： Status InitStack(TwoWayStack &tws, int size); Status Push(TwoWayStack &tws, int i, SElemType x); Status Pop(TwoWayStack &tws, int i, SElemType &x); 双向栈类型定义如下： typedef struct { SElemType *elem; int top[2]; int size; // 分配给elem的总容量 }TwoWayStack; // 双端栈 Status InitStack(TwoWayStack &tws, int size){ tws.elem=(SElemType*)malloc(sizeof(SElemType)*size); tws.size=size; tws.top[0]=0; //hao tws.top[1]=size-1; //以数组下标作为指针； return OK; } Status Push(TwoWayStack &tws, int i, SElemType x) {int w=tws.top[0]; if(w==tws.top[1]) return ERROR; else if(i==0) { tws.elem[tws.top[0]]=x; tws.top[0]=tws.top[0]+1; } else if(i==1) { tws.elem[tws.top[1]]=x; tws.top[1]=tws.top[1]-1; } return OK; 华北科技学院计算机系综合性实验 实验报告 课程名称 C语言程序设计 实验学期 2011 至 2012 学年第二学期学生所在系部计算机系 年级 2011 专业班级计算机科学与技术B-111 学生姓名学号 任课教师 实验成绩 计算机系制 实验报告须知 1、学生上交实验报告时，必须为打印稿（A4纸）。页面空间不够，可以顺延。 2、学生应该填写的内容包括：封面相关栏目、实验地点、时间、目的、设备环境、 内容、结果及分析等。 3、教师应该填写的内容包括：实验成绩、教师评价等。 4、教师根据本课程的《综合性实验指导单》中实验内容的要求，评定学生的综合 性实验成绩；要求在该课程期末考试前将实验报告交给任课教师。综合性实验中，所涉及的程序，文档等在交实验报告前，拷贝给任课教师。任课教师统一刻录成光盘，与该课程的期末考试成绩一同上交到系里存档。 5、未尽事宜，请参考该课程的实验大纲和教学大纲。 《C语言程序设计》课程综合性实验报告 实验题目基于链表的学生成绩管理系统 一、实验目的 1、掌握链表的创建、遍历显示和清除； 2、掌握链表数据的文件保存、读取； 二、设备与环境 微型计算机、VC++ 三、实验内容 1、定义结构体，创建链表 struct xsnode { int xh; char xm[15]; int gs; int yy; int wl; struct xsnode *next; }; 2、根据以上链表结点结构，实现以下功能 a、学生学号、姓名、各门成绩的录入； b、链表数据显示及清除； c、链表数据的文件保存与读取； 四、实验结果及分析 1、运行结果 主菜单 链表的C语言实现之单链表的实现 https://www.wendangku.net/doc/f34085049.html,/article/2779.html 一、单链表的建立 有了动态内存分配的基础，要实现链表就不难了。 所谓链表，就是用一组任意的存储单元存储线性表元素的一种数据结构。链表又分为单链表、双向链表和循环链表等。我们先讲讲单链表。所谓单链表，是指数据接点是单向排列的。一个单链表结点，其结构类型分为两部分： 1、数据域：用来存储本身数据 2、链域或称为指针域：用来存储下一个结点地址或者说指向其直接后继的指针。 例： typedef struct node { char name[20]; struct node *link; }stud; 这样就定义了一个单链表的结构，其中char name[20]是一个用来存储姓名的字符型数组，指针*link是一个用来存储其直接后继的指针。 定义好了链表的结构之后，只要在程序运行的时候爱数据域中存储适当的数据，如有后继结点，则把链域指向其直接后继，若没有，则置为NULL。 下面就来看一个建立带表头（若未说明，以下所指链表均带表头）的单链表的完整程序。 #include ＜stdio.h＞ #include ＜malloc.h＞ /*包含动态内存分配函数的头文件*/ #define N 10 /*N为人数*/ typedef struct node { char name[20]; struct node *link; }stud; stud * creat(int n) /*建立单链表的函数，形参n为人数*/ { stud *p,*h,*s; /* *h保存表头结点的指针，*p指向当前结点的前一个结点，*s指向当前结点*/ int i; /*计数器*/ if((h=(stud *)malloc(sizeof(stud)))==NULL) /*分配空间并检测*/ { printf("不能分配内存空间!"); exit(0); } h-＞name[0]='\0'; /*把表头结点的数据域置空*/ h-＞link=NULL; /*把表头结点的链域置空*/ p=h; /*p指向表头结点*/ for(i=0;i＜n;i++) { 附录A 实验报告 课程：数据结构（c语言）实验名称：栈和队列 系别：数字媒体技术实验日期： 11月15号 专业班级：组别： 姓名：学号： 实验报告内容 验证性实验 一、预习准备： 实验目的： 1. 掌握栈的顺序表示、链表表示以及相应操作的实现。特别注意栈空和栈满 的条件； 2. 掌握队列的顺序表示、链表表示以及相应操作的实现。特别是循环队列中 队头与队尾指针的变化情况； 实验环境：Widows操作系统、VC6.0 实验原理： 1.定义： 栈：只允许在一端插入和删除的线性表，允许插入和删除的一端称为 栈顶(top)，另一端称为栈底(bottom)。 队列: 是只允许在一端删除，在另一端插入的顺序表,允许删除的一端叫做队 头(front)，允许插入的一端叫做队尾(rear)。 2.特点： 栈：后进先出(LIFO) 队列：先进先出(FIFO, First In First Out) 9 3. 表示： 栈：（1）栈的数组表示—顺序栈 （2）栈的链接表示—链式栈 队列：（1）队列的顺序存储结构表示——循环队列 （2）队列的链式表示—链队列 实验内容和要求： 分别使用顺序循环队列和堆栈以及链式队列和堆栈编写程序：判断一个字符序列是否是回文。回文是指一个字符序列以中间字符为基准，两边字符完全相同。如：“ABCDEDCBA”。字符串长度小于等于80，用于判断回文的字符串不包括字符串的结束标记符。 基本要求： （1）字符序列可由用户从键盘随意输入； （2）可以连续测试多个字符序列，由用户决定退出测试程序； 算法思想： 判断回文的算法思想是：把字符串中的字符逐个分别存入队列和堆栈中，然后逐个出队列和退栈并比较出队列的数据元素和退栈的数据元素是否相等，若全部相等则该字符序列为回文，否则就不是回文。 基本操作： 回文判断操作主要包括入栈和入队列、退栈和出队列操作。在对堆栈以及队列进行操作之前，必须对队列以及堆栈进行初始化。若使用链式堆栈和链式队列，操作结束后必须销毁链表。 二、实验过程： 程序流程图： 单链表 带头结点 #include struct node *s; int n; while(1) { scanf("%d",&n); /*根据实际情况判断链表的元素 输入结束 还有一种情况就是找不到合适的 作为结束标记的值 先让用户输入元素个数， 然后固定字数循环*/ if(n==-1) break; /* 创建新结点 */ s = (struct node *)malloc(sizeof(struct node)); s->data = n; s->next = h->next; /* 新结点放入链表的表头 让头结点的NEXT指向新结点 */ h->next = s; (h->data)++; } } /* 遍历整个链表 */ void bianliLink(struct node *h) { int k; struct node *p; /* P指向第一个结点 */ p=h->next; /* 如果定义了链表长度变量， 可以使用变量计数， 表示处理到链表的最后一个元素 如果不定义链表长度变量， 就用指针是否指向NULL， 判断是否处理到最后一个元素了 单链表完整C语言纯代码 单链表 带头结点 #include void init(struct node **h) { struct node *s; s = (struct node *)malloc(sizeof(struct node)); if(s==NULL) return; /* 头结点的数据域存储链表的长度 */ s->data=0; s->next=NULL; /*让头指针指向头结点*/ *h = s; } /* 创建链表，仍然按照逆序创建， 从后往前输入元素的值， 然后把新结点插入到表头 */ void createLink(struct node *h) { struct node *s; int n; while(1) { scanf("%d",&n); /*根据实际情况判断链表的元素 输入结束 还有一种情况就是找不到合适的 作为结束标记的值 先让用户输入元素个数， 然后固定字数循环*/ if(n==-1) break; /* 创建新结点 */ s = (struct node *)malloc(sizeof(struct node)); s->data = n; s->next = h->next; /* 新结点放入链表的表头 让头结点的NEXT指向新结点 */ 建立了一个单链表之后，如果要进行一些如插入、删除等操作该怎么办？所以还须掌握一些单链表的基本算法，来实现这些操作单链表的基本运算包括：查找、插入和删除下面我们就一一介绍这三种基本运算的算法，并结合我们建立单链表的例子写出相应的程序 1、查找 对单链表进行查找的思路为：对单链表的结点依次扫描，检测其数据域是否是我们所要查好的值，若是返回该结点的指针，否则返回null 因为在单链表的链域中包含了后继结点的存储地址，所以当我们实现的时候，只要知道该单链表的头指针，即可依次对每个结点的数据域进行检测 以下是应用查找算法的一个例子： #include ＜stdio.h＞ #include ＜malloc.h＞ #include ＜string.h＞/*包含一些字符串处理函数的头文件*/ #define n 10 typedef struct node { char name[20]; struct node *link; }stud; stud * creat(int n) /*建立链表的函数*/ { stud *p,*h,*s; int i; if((h=(stud *)malloc(sizeof(stud)))==null) { printf(\"不能分配内存空间!\"); exit(0); } h-＞name[0]=\'\\0\'; h-＞link=null; p=h; for(i=0;i＜n;i++) { if((s= (stud *) malloc(sizeof(stud)))==null) { printf(\"不能分配内存空间!\"); exit(0); } p-＞link=s; 链表的C语言实现 分类:计算机学习 2006.12.29 09:06 作者：ybxycy | 评论：0 | 阅读：652 数组作为存放同类数据的集合，给我们在程序设计时带来很多的方便，增加了灵活性。但数组也同样存在一些弊病。如数组的大小在定义时要事先规定，不能在程序中进行调整，这样一来，在程序设计中针对不同问题有时需要3 0个大小的数组，有时需要5 0个数组的大小，难于统一。我们只能够根据可能的最大需求来定义数组，常常会造成一定存储空间的浪费。 我们希望构造动态的数组，随时可以调整数组的大小，以满足不同问题的需要。链表就是我们需要的动态数组。它是在程序的执行过程中根据需要有数据存储就向系统要求申请存储空间，决不构成对存储区的浪费。 链表是一种复杂的数据结构，其数据之间的相互关系使链表分成三种：单链表、循环链表、双向链表，下面将逐一介绍。 7.4.1 单链表 图7 - 3是单链表的结构。 单链表有一个头节点h e a d，指向链表在内存的首地址。链表中的每一个节点的数据类型为结构体类型，节点有两个成员：整型成员（实际需要保存的数据）和指向下一个结构体类型节点的指针即下一个节点的地址（事实上，此单链表是用于存放整型数据的动态数组）。链表按此结构对各节点的访问需从链表的头找起，后续节点的地址由当前节点给出。无论在表中访问那一个节点，都需要从链表的头开始，顺序向后查找。链表的尾节点由于无后续节点，其指针域为空，写作为N U L L。 图7 - 3还给出这样一层含义，链表中的各节点在内存的存储地址不是连续的，其各节点的地址是在需要时向系统申请分配的，系统根据内存的当前情况，既可以连续分配地址，也可以跳跃式分配地址。 C语言课程设计职工信息管理系统单链表实现 程序源代码 文档编制序号：[KKIDT-LLE0828-LLETD298-POI08] 有%d条记录已经保存.)\n",count); saveflag=0; } else { system("cls"); printf("保存文件失败，'0'条记录被保存！\n"); } fclose(fp); } xt","ab+"); else exit(0); } ....\n"); while(!feof(fp)) n",count); while(1) { menu(); printf("\t\t====>请选择："); scanf("%d",&choose); if(choose==0) { if(saveflag==1) { getchar(); printf("\n=====>提示:资料已经改动,是否将改动保存到文件中(y/n)\n"); scanf("%c",&ch); if(ch=='y'||ch=='Y') Save(list); } //if printf("\n=====>提示:你已经退出系统,再见!\n"); break; }//if switch(choose) { case 1:Add(list); break; /* 增加职工记录 */ case 2: Del(list); break;/* 删除职工记录 */ case 3: Qur(list); break;/* 查询职工记录 */ case 4: Modify(list); break;/* 修改职工记录 */ case 5: Insert(list); break;/*插入职工记录*/ case 6: Tongji(list); break;/*统计职工记录*/ case 7: Sort(list); break;/*排序职工记录*/ case 8: Save(list); break;/* 保存职工记录 */ case 9: system("cls"); Disp(list); break; /*显示职工记录*/ default: Wrong(); getchar(); break; } //switch(choose) }//while(1) } //main() /* */ 1)插入操作 在顺序表L的第i(1<=L.length+1)个位置插入新元素e。如果i的输入不合法，则返回false，表示插入失败；否则，将顺序表的第i个元素以及其后的元素右移一个位置，腾出一个空位置插入新元素e，顺序表长度增加1，插入成功，返回true。 1.bool ListInsert(SqList&L,int i,ElemType e){ 2.//本算法实现将元素e插入到顺序表L中第i个位置 3.if(i<1||i>L.length+1) 4.return false;//判断i的范围是否有效 5.if(L.length>=MaxSize) 6.return false;//当前存储空间已满，不能插入 7.for(int j=L.length;j>=i;j--)//将第i个位置及之后的元素后移 8.L.data[j]=L.data[j-l]; 9.L.data[i-1]=e;//在位置i处放入e 10.L.length++;//线性表长度加1 11.return true; 12.} 2)删除操作 删除顺序表L中第i(1<=i<=L.length)个位置的元素，成功则返回true,否则返回false，并将被删除的元素用引用变量e返回。 复制纯文本新窗口 1.bool ListDelete(SqList&L,int i,int&e){ 2.//本算法实现删除顺序表L中第i个位置的元素 3.if(i<1||i>L.length) 4.return false;//判断i的范围是否有效 5.e=L.data[i-1];//将被删除的元素赋值给e 6.for(int j=i;j 链表专题复习 数组作为存放同类数据的集合，给我们在程序设计时带来很多的方便，增加了灵活性。但数组也同样存在一些弊病。如数组的大小在定义时要事先规定，不能在程序中进行调整，这样一来，在程序设计中针对不同问题有时需要 3 0个元素大小的数组，有时需要 5 0个数组元素的大小，难于统一。我们只能够根据可能的最大需求来定义数组，常常会造成一定存储空间的浪费。 我们希望构造动态的数组，随时可以调整数组的大小，以满足不同问题的需要。链表就是我们需要的动态数组。它是在程序的执行过程中根据需要有数据存储就向系统要求申请存储空间，决不构成对存储区的浪费。 链表是一种复杂的数据结构，其数据之间的相互关系使链表分成三种：单链表、循环链表、双向链表，下面只介绍单向链表。 7.4.1 单链表 图7 - 3是单链表的结构。 单链表有一个头节点h e a d，指向链表在内存的首地址。链表中的每一个节点的数据类型为结构体类型，节点有两个成员：整型成员（实际需要保存的数据）和指向下一个结构体类型节点的指针即下一个节点的地址（事实上，此单链表是用于存放整型数据的动态数组）。链表按此结构对各节点的访问需从链表的头找起，后续节点的地址由当前节点给出。无论在表中访问那一个节点，都需要从链表的头开始，顺序向后查找。链表的尾节点由于无后续节点，其指针域为空，写作为N U L L。 图7 - 3还给出这样一层含义，链表中的各节点在内存的存储地址不是连续的，其各节点的地址是在需要时向系统申请分配的，系统根据内存的当前情况，既可以连续分配地址，也可以跳跃式分配地址。 看一下链表节点的数据结构定义： struct node { int num; struct node *p; } ; 在链表节点的定义中，除一个整型的成员外，成员p是指向与节点类型完全相同的指针。 在链表节点的数据结构中，非常特殊的一点就是结构体内的指针域的数据类型使用了未定义成功的数据类型。这是在C中唯一规定可以先使用后定义的数据结构。 ?单链表的创建过程有以下几步： 1 ) 定义链表的数据结构。 2 ) 创建一个空表。 3 ) 利用m a l l o c ( )函数向系统申请分配一个节点。 XXXX学院 计算机课程实验报告（201X～201X年度第X学期） 专业 课程数据结构 班级 组别 教师 琼州学院电子信息工程学院制 实验报告填写说明 1、填写一律用钢笔或圆珠笔填写，要求字迹工整，条理 清晰。 2、“实验题目”可以填写章节名称或用文字表述。 3、“实验目的”要逐条列出，“实验内容”以简练的文 字进行概括。 4、“附注”处填写实验注意事项或调试过程，以及实验 中出现的异常情况和解决方法。 5、“教师批阅”处有课任老师填写评语，给出实验成绩， 并作为平时成绩，参与期末成绩总评。 6、封面和实验报告填写说明正反面打印在一张纸上。 201X年XX月XX日 实验项目：栈及队列的链式和线性存储以及相关操作实现实验目的： 1.掌握数据结构中栈及队列的链式和线性存储结构操作; 2.了解数据结构中栈及队列的基本操作原理 3.掌握C语言中基本程序设计的方法. 4.掌握基本测试方法。 实验仪器： 计算机、C语言版数据结构相关实验题集、编写程序软件 实验规划：（包括函数说明、公共变量说明、测试说明等） 公共变量声明： #include C语言课程设计报告 链表实现学生信息管理 一．课程设计目标 C语言课程设计的目的是通过课程设计的综合训练，培养学生实际分析问题、编程和动手能力，最终目标是通过这种形式，帮助学生系统掌握该门课程的主要容，更好地完成教学任务。本课程设计具有如下特点：重点在于C语言的基本特征上，涵盖了C语言的重要基础知识。结合了实际应用的要求，使课程设计既涵盖知识点，又接近工程实际需要。通过激发学习兴趣，调动学生主动学习的积极性，并引导他们根据实际编程要求，训练自己实际分析问题的能力以及编程能力，并养成良好的编程习惯。 另外，在实际编程中，为了提高编程质量，希望学生在书写代码时，对空行、空格和注释严格按要求处理，以建立良好的编程风格。 二．设计项目：学生学籍管理 该课程设计是设计一个模拟学生信息管理程序，要求使用链表来实现。它具有浏览、插入、删除、修改等功能，并且能够对数据进行文件存储和读出操作。 主要功能模块： 1. 浏览学生信息：显示学生的信息。 2. 插入学生信息：添加学生的信息。 3. 删除学生信息：通过输入学号删除学生的信息。 4. 修改学生信息：通过输入学号修改学生的信息。 5. 保存学生信息：将学生信息保存到文件。 0. 退出系统：结束程序的运行，结束前询问是否保存信息。 三．具体任务 由老师提供主菜单程序以及第0、2个模块。 学生在这个信息系统中加入四个模块,即: 1. 浏览学生信息 3. 删除学生信息 4. 修改学生信息 5. 保存学生信息 四、详细介绍 1、浏览学生信息 2、插入学生信息 3、删除学生信息 4、修改学生信息 #include<> #define null 0 #define len sizeof(struct lnode) int n; struct lnode *creatlist(); struct lnode *listinsert(); struct lnode *listdel(); struct lnode{ int a; struct lnode *next; }; struct lnode *head; void main() { int n; do{ printf("=====链式表练习=====\n"); printf(" 请选择操作：\n"); printf(" 1、建立链式表\n"); printf(" 2、插入新元素\n"); printf(" 3、删除元素\n"); printf("====================\n"); scanf("%d",&n); switch(n) { case 1:creatlist();break; case 2:listinsert();break; case 3:listdel();break; default:printf("选择错误，请确认输入！\n");break; } }while(1); } struct lnode *creatlist()//建立链表 { struct lnode *p1,*p2,*p0; n=0; head=null; p1=(struct lnode *)malloc(len); printf("请输入初始元素：\n"); scanf("%d",&p1->a); p1->next=null; while(p1->a!=0) { 链表的c语言实现（一） 准备：动态内存分配 一、为什么用动态内存分配 但我们未学习链表的时候，如果要存储数量比较多的同类型或同结构的数据的时候，总是使用一个数组。比如说我们要存储一个班级学生的某科分数，总是定义一个float型（存在0.5分）数组： float score[30]; 但是，在使用数组的时候，总有一个问题困扰着我们：数组应该有多大？ 在很多的情况下，你并不能确定要使用多大的数组，比如上例，你可能并不知道该班级的学生的人数，那么你就要把数组定义得足够大。这样，你的程序在运行时就申请了固定大小的你认为足够大的内存空间。即使你知道该班级的学生数，但是如果因为某种特殊原因人数有增加或者减少，你又必须重新去修改程序，扩大数组的存储范围。这种分配固定大小的内存分配方法称之为静态内存分配。但是这种内存分配的方法存在比较严重的缺陷，特别是处理某些问题时：在大多数情况下会浪费大量的内存空间，在少数情况下，当你定义的数组不够大时，可能引起下标越界错误，甚至导致严重后果。 那么有没有其它的方法来解决这样的外呢体呢？有，那就是动态内存分配。 所谓动态内存分配就是指在程序执行的过程中动态地分配或者回收存储空间的分配内存的方法。动态内存分配不象数组等静态内存分配方法那样需要预先分配存储空间，而是由系统根据程序的需要即时分配，且分配的大小就是程序要求的大小。从以上动、静态内存分配比较可以知道动态内存分配相对于景泰内存分配的特点： 1、不需要预先分配存储空间； 2、分配的空间可以根据程序的需要扩大或缩小。 二、如何实现动态内存分配及其管理 要实现根据程序的需要动态分配存储空间，就必须用到以下几个函数 1、malloc函数 malloc函数的原型为： void *malloc (unsigned int size)C语言链表功能实现
数据结构与算法C语言版期末复习题
《数据结构(C语言版)》复习重点要点
数据结构(C语言版) 期末复习汇总
详解堆栈的几种实现方法——C语言版
C语言课程设计_职工信息管理系统_单链表实现程序源代码
数据结构(C语言版)例题(第三章：栈和队列)
C语言程序设计-基于链表的学生成绩管理系统
081103_链表的C语言实现之单链表的实现
实验报告(栈和队列)
单链表完整C语言纯代码
单链表完整C语言纯代码
链表的C语言实现之单链表的查找运算
链表的C语言实现
C语言课程设计职工信息管理系统单链表实现程序源代码
数据结构C语言版算法大全
C语言链表专题复习
数据结构(栈及队列)实验报告 C语言版
c语言程序设计报告链表实现学生信息管理
c语言栈队列链表算法代码实现
链表的c语言实现(一)
- C语言链表专题复习
- 链表的C语言实现之动态内存分配
- 单链表的C语言实现
- C语言链表图书管理系统
- C语言实现链表操作
- c语言程序设计报告链表实现学生信息管理
- 单向链表-C语言实现.c
- 最全的c语言链表大全
- 单链表完整C语言纯代码
- C语言课程设计职工信息管理系统单链表实现程序源代码
- 单链表C语言实现
- C语言链表功能实现
- C语言课程设计_职工信息管理系统_单链表实现程序源代码
- 链表的C语言实现之单链表的查找运算
- c语言中创建动态链表
- 通讯录管理系统数据结构C语言版链表实现实验报告
- C语言实现单链表的增删改查
- 081103_链表的C语言实现之单链表的实现
- 链表的C语言实现
- 单链表的基本操作 C语言课程设计