当前位置:文档之家› 2014辽宁省C与数据结构链表(必备资料)

2014辽宁省C与数据结构链表(必备资料)

2014辽宁省C与数据结构链表(必备资料)
2014辽宁省C与数据结构链表(必备资料)

1、下面程序段的时间复杂度是( A )。

s =0;

for( i =0; i

for(j=0;j

s +=B[i][j];

sum = s ;

A) O(n2) B) O(n)

C) O(m*n) D)O(1)

2、若采用邻接矩阵法存储一个n个顶点的无向图,则该邻接矩阵是一个( D )。

A)上三角矩阵 B) 稀疏矩阵

C) 对角矩阵 D) 对称矩阵

3、若采用邻接矩阵法存储一个n个顶点的无向图,则该邻接矩阵是一个( D )。

A)上三角矩阵 B) 稀疏矩阵

C) 对角矩阵 D) 对称矩阵

4、下列序列中,执行第一趟快速排序后得到的序列是( A )。

A)[d,a,e,d,b]f[h,g] B) [c,e,a,d]f[h,g,b]

C) [g,a,e,c,b]f[d,h] D) [a,b,c,d,]f[e,g,h]

5、若采用邻接矩阵法存储一个n个顶点的无向图,则该邻接矩阵是一个( D )。

A)上三角矩阵 B) 稀疏矩阵

C) 对角矩阵 D) 对称矩阵

6、已知广义表L=((x,y,z),a,(u,t,w)),从L 表中取出原子项t 的操作是( D )。

A) Head(Head(Tail(Tail(L))))

B) Tail(Head(Head(Tail(L))))

C) Head(Tail(Head(Tail(L))))

D)Head(Tail(Head(Tail(Tail(L)))))

7、在一个链队列中,假定front和rear分别为队首和队尾指针,则插入一个结点的操作为( B )。

A)front=front->next; B) rear=rear->next;

C) rear=front->next; D) front=rear->next ;

8、设给定问题的规模为变量n,解决该问题的算法所需时间为Tn=O(f(n)),Tn表示式中记号O表示( A )。

A)一个数量级别 B)一个平均值

C)一个最大值 D)一个均方值

9、已知栈的最大容量为4。若进栈序列为1,2,3,4,5,6,且进栈和出栈可以穿插进行,则可能出现的出栈序列为( C )。

A) 5,4,3,2,1,6 B) 2,3,5,6,1,4

C) 3,2,5,4,1,6 D) 1,4,6,5,2,3

10、在一个具有n个单元的顺序栈中,假定以地址低端(即0单元)作为栈底,以top作为栈顶指针,当做出栈处理时,top变化为( C )。

A)top不变 B)top=0 C)top-- D)top++

11、广义表A=(A,B,(C,D),(E,(F,G))),则head(tail(head(tail(tail(A)))))=( D )。 A) (G) B) (D) C) C D) D

12、设单链表中指针p指着结点A,若要删除A之后的结点(若存在),则需要修改指针的操作为( A )。

A)p->next=p->next->next B)p=p->next

C)p=p->nexe->next D)p->next=p

13、( C )在进行插入操作时,常产生假溢出现象。

A)顺序栈 B)循环队列

C)顺序队列 D)链队列

14、链式存储的存储结构所占存储空间( A )。

A)分两部分,一部分存放结点值,另一部分存放表示结点间关系的指针

B)只有一部分,存放结点值

C)只有一部分,存储表示结点间关系的指针

D)分两部分,一部分存放结点值,另一部分存放结点所占单元数

15、倘若在对串的插入、删除运算中,期望运算速度最快,则应采用( C )。

A)顺序表示法 B)单字符为结点的单链表表示法

C)等量分块表示法 D)不等量分块表示法

16、链式存储的存储结构所占存储空间( A )。

A)分两部分,一部分存放结点值,另一部分存放表示结点间关系的指针

B)只有一部分,存放结点值

C)只有一部分,存储表示结点间关系的指针

D)分两部分,一部分存放结点值,另一部分存放结点所占单元数

数据结构—链表应用能力测评

任务: 编写一个能向表尾插入结点,并输出链表中所有数据元素的小程序

#ifndef _LINKLIST #define _LINKLIST #include using namespace std ; struct node { int data ; struct node *next ; }; typedef struct node *PLIST; typedef struct node NODE; /*创建链表,并初始化链表元素*/ PLIST createList_link() { PLIST head ,tail ,temp; int elem = -1; head = new NODE; //初始化头结点 if( head == NULL) { cout<<"分配空间失败,链表创建失败"<next = NULL; tail = head ; while(1) { cin >> elem ; if(elem == 0 ) break ; temp = new NODE ; if(temp == NULL) { cout<<"分配空间失败,链表创建失败"<data = elem ; temp->next = NULL ; tail->next = temp ; tail = temp; } return head ;

} void printList_link(PLIST head ) { /*在此处完成任务,输出head为表头的单链表数据元素*/ //begin PLIST p =new NODE; p=head->next; while(p){ printf("%d ",p->data); p=p->next; } //end } void insertDataTail(PLIST head , int insData ) { /*在此处完成任务,在head为表头的单链表表尾插入数据元素insData*/ //begin PLIST p; p=head->next; while(p->next!=NULL){ p=p->next; } PLIST q = new NODE; //初始化结点 p->next=q; q->data=insData; q->next=NULL; //end } #endif

城市链表实验报告

2014-2015学年第一学期实验报告 课程名称:算法与数据结构 实验名称:城市链表

一、实验目的 本次实验的主要目的在于熟悉线性表的基本运算在两种存储结构上的实现,其中以熟悉各种链表的操作为侧重点。同时,通过本次实验帮助学生复习高级语言的使用方法。 二、实验内容 (一)城市链表: 将若干城市的信息,存入一个带头结点的单链表。结点中的城市信息包括:城市名,城市的位置坐标。要求能够利用城市名和位置坐标进行有关查找、插入、删除、更新等操作。 (二) 约瑟夫环 m 的初值为20;密码:3,1,7,2,6,8,4(正确的结果应为6,1,4,7,2,3,5)。三、实验环境 VS2010 、win8.1 四、实验结果 (一)城市链表: (1)创建城市链表; (2)给定一个城市名,返回其位置坐标; (3)给定一个位置坐标P 和一个距离D,返回所有与P 的距离小于等于 D 的城市。 (4)在已有的城市链表中插入一个新的城市; (5)更新城市信息; (6)删除某个城市信息。 (二) 约瑟夫环 m 的初值为20;密码:3,1,7,2,6,8,4 输出6,1,4,7,2,3,5。 五、附录 城市链表: 5.1 问题分析 该实验要求对链表实现创建,遍历,插入,删除,查询等操作,故使用单链表。

5.2 设计方案 该程序大致分为以下几个模块: 1.创建城市链表模块,即在空链表中插入新元素。故创建城市链表中包涵插入模块。 2.返回位置坐标模块。 3.计算距离模块 4.插入模块。 5.更新城市信息模块 6.删除信息模块。 5.3 算法 5.3.1 根据中心城市坐标,返回在距离内的所有城市: void FindCityDistance(citylist *L){ //根据距离输出城市 ……//输入信息与距离 L=L->next; w hile(L != NULL){ if(((L->x-x1)*(L->x-x1)+(L->y-y1)*(L->y-y1 )<=dis*dis)&&(((L->x-x1)+(L->y-y1))!=0 )){ printf("城市名称%s\n",L->Name); printf("城市坐标%.2lf,%.2lf\n",L->x,L->y); } L=L->next; } } 该算法主要用到了勾股定理,考虑到不需要实际数值,只需要大小比较,所以只用 横坐标差的平方+纵坐标差的平方<= 距离的平方判定。

数据结构 单链表详解

数据结构的概念: 数据的逻辑结构+ 数据的存储结构+ 数据的操作; 数据的数值:=====》数据===》数值型数据整形浮点数ASCII 非数值型数据图片声音视频字符 =====》数据元素=====》基本项组成(字段,域,属性)的记录。 数据的结构: 逻辑结构 ----》线性结构(线性表,栈,队列) ----》顺序结构 ----》链式结构 ----》非线性结构(树,二叉树,图) ----》顺序结构 ----》链式结构 存储结构 -----》顺序存储 -----》链式存储 -----》索引存储 -----》哈希存储==散列存储 数据的操作: 增 删 改 查 DS ====》数据结构===》DS = (D,R); 数据结构中算法: 1、定义:有穷规则的有序集合。 2、特性: 有穷性 确定性

输入 输出 3、算法效率的衡量 时间复杂度计算===》算法中可执行依据的频度之和,记为:T(n)。 是时间的一种估计值不是准确值。 计算结果的分析:1 将最终结果的多项式中常数项去掉 2 只保留所有多项式中最高阶的项 3 最后的最高阶项要去掉其常数项 时间复杂度的量级关系: 常量阶====》对数阶===》线性阶===》线性对数阶====》平方阶===》立方阶===》指数阶 以上关系可以根据曲线图来判断算法对时间复杂度的要求 空间复杂度计算====》算法执行过程中所占用的存储空间的量级,记为:D(n)。 计算方法是在运行过程中申请的动态内存的量级计算。 ///////////////////////////////////////////////////////////////////////////////////////////////// 线性表 顺序存储====》顺序表(数组) 链式存储====》单链表 特征:对于非空表,a0是表头没有前驱。 an-1 是表尾没有后继 ai的每个元素都有一个直接前驱和直接后继 基本操作:创建表=====》增加元素====》删除元素====》改变元素值====》查询元素 1、顺序表的操作 1.1 创建顺序表=====》定义个指定类型的数组====》int a[100] ={0};

数据结构 单链表基本操作代码

实验一单链表 #include "stdio.h" #include "stdlib.h" typedef int ElemType; typedef struct LNode { ElemType data; struct LNode *next; }LNode,*LinkList; void creatLNode(LinkList &head) { int i,n; LNode *p; head=(LNode*)malloc(sizeof(LNode)); head->next=NULL; printf("请输入链表的元素个数:"); scanf("%d",&n); for(i=n;i>0;i--) { p=(LNode*)malloc(sizeof(LNode)); printf("第%d个元素:",i); scanf("%d",&p->data); p->next=head->next; head->next=p; } } void InsertLNode(LinkList &L) { LNode *p=L; int i,j=0,e; printf("请输入你要插入的位置(超过链表长度的默认插在最后!):"); scanf("%d",&i); printf("请输入你要插入的元素:"); scanf("%d",&e); while (p->next&&jnext; ++j; }

LNode *s; s=(LNode*)malloc(sizeof(LNode)); s->data=e; s->next=p->next; p->next=s; } int DeleteLNode(LinkList &L,int i,int &e) { LNode *p; p=L; LNode *q; int j=0; while (p->next&&jnext; ++j; } if(!(p->next)||j>i-1) { printf("删除位置不合理!\n"); return 0; } q=p->next; p->next=q->next; e=q->data; free(q); return e; } void DeleteCF(LinkList &L) { LNode *p,*s,*r; p=L->next; while(p!=NULL) { r=p; s=r->next; while(s!=NULL) { if(p->data==s->data) { r->next=s->next; s=s->next;

链表实验报告

链表实验报告

————————————————————————————————作者: ————————————————————————————————日期:

《数据结构》实验报告二 系别:嵌入式系统工程系班级:嵌入式11003班 学号:11160400314姓名:孙立阔 日期:2012年4月9日指导教师:申华 一、上机实验的问题和要求: 单链表的查找、插入与删除。设计算法,实现线性结构上的单链表的产生以及元素的查找、插入与删除。具体实现要求: 1.从键盘输入10个字符,产生不带表头的单链表,并输入结点值。 2.从键盘输入1个字符,在单链表中查找该结点的位置。若找到,则显示“找到了”;否则, 则显示“找不到”。 3.从键盘输入2个整数,一个表示欲插入的位置i,另一个表示欲插入的数值x,将x插 入在对应位置上,输出单链表所有结点值,观察输出结果。 4.从键盘输入1个整数,表示欲删除结点的位置,输出单链表所有结点值,观察输出结果。 5.将单链表中值重复的结点删除,使所得的结果表中个结点值均不相同,输出单链表所有结 点值,观察输出结果。 6.删除其中所有数据值为偶数的结点,输出单链表所有结点值,观察输出结果。 7.(★)将单链表分解成两个单链表A和B,使A链表中含有原链表中序号为奇数的元素, 而B链表中含有原链表中序号为偶数的元素,且保持原来的相对顺序,分别输出单链表A和单链表B的所有结点值,观察输出结果。 二、程序设计的基本思想,原理和算法描述: (包括程序的结构,数据结构,输入/输出设计,符号名说明等) 创建一个空的单链表,实现对单链表的查找,插入,删除的功能。 三、源程序及注释: #defineOK 1 #define ERROR 0 #define INFEASIBLE -1 #define OVERFLOW -2 #define TRUE 1

数据结构课程设计单链表

目录 1 选题背景 (2) 2 方案与论证 (3) 2.1 链表的概念和作用 (3) 2.3 算法的设计思想 (4) 2.4 相关图例 (5) 2.4.1 单链表的结点结构 (5) 2.4.2 算法流程图 (5) 3 实验结果 (6) 3.1 链表的建立 (6) 3.2 单链表的插入 (6) 3.3 单链表的输出 (7) 3.4 查找元素 (7) 3.5 单链表的删除 (8) 3.6 显示链表中的元素个数(计数) (9) 4 结果分析 (10) 4.1 单链表的结构 (10) 4.2 单链表的操作特点 (10) 4.2.1 顺链操作技术 (10) 4.2.2 指针保留技术 (10) 4.3 链表处理中的相关技术 (10) 5 设计体会及今后的改进意见 (11) 参考文献 (12) 附录代码: (13)

1 选题背景 陈火旺院士把计算机60多年的发展成就概括为五个“一”:开辟一个新时代----信息时代,形成一个新产业----信息产业,产生一个新科学----计算机科学与技术,开创一种新的科研方法----计算方法,开辟一种新文化----计算机文化,这一概括深刻影响了计算机对社会发展所产生的广泛而深远的影响。 数据结构和算法是计算机求解问题过程的两大基石。著名的计算机科学家P.Wegner指出,“在工业革命中其核心作用的是能量,而在计算机革命中其核心作用的是信息”。计算机科学就是“一种关于信息结构转换的科学”。信息结构(数据结构)是计算机科学研究的基本课题,数据结构又是算法研究的基础。

2 方案与论证 2.1 链表的概念和作用 链表是一种链式存储结构,链表属于线性表,采用链式存储结构,也是常用的动态存储方法。链表中的数据是以结点来表示的,每个结点的构成:元素(数据元素的映象) + 指针(指示后继元素存储位置),元素就是存储数据的存储单元,指针就是连接每个结点的地址数据。 以“结点的序列”表示线性表称作线性链表(单链表) 单链表是链式存取的结构,为找第 i 个数据元素,必须先找到第 i-1 个数据元素。 因此,查找第 i 个数据元素的基本操作为:移动指针,比较 j 和 i 单链表 1、链接存储方法 链接方式存储的线性表简称为链表(Linked List)。 链表的具体存储表示为: ① 用一组任意的存储单元来存放线性表的结点(这组存储单元既可以是连续的,也可以是不连续的) ② 链表中结点的逻辑次序和物理次序不一定相同。为了能正确表示结点间的逻辑关系,在存储每个结点值的同时,还必须存储指示其后继结点的地址(或位置)信息(称为指针(pointer)或链(link)) 注意: 链式存储是最常用的存储方式之一,它不仅可用来表示线性表,而且可用来表示各种非线性的数据结构。 2、链表的结点结构 ┌───┬───┐ │data │next │ └───┴───┘ data域--存放结点值的数据域 next域--存放结点的直接后继的地址(位置)的指针域(链域) 注意: ①链表通过每个结点的链域将线性表的n个结点按其逻辑顺序链接在一起的。 ②每个结点只有一个链域的链表称为单链表(Single Linked List)。

数据结构课程设计单链表操作

《数据结构课程设计》报告 题目:单链表操作 专业:计算机科学与技术 班级: 单链表操作 针对带头结点的单循环链表,编写实现以下操作的算法函数。

实现要求: ⑴单链表建立函数create:先输入数据到一维数组A[M]中,然后根据一维 数组A[M]建立一个单循环链表,使链表中个元素的次序与A[M]中各元素的次序相同,要求该函数的时间复杂度为O(m); ⑵定位查找函数Locate:在所建立的单循环链表中查找并返回值为key的 第1个元素的结点指针;若找不到,则返回NULL; ⑶求出该链表中值最大和次大的元素值,要求该算法的时间复杂度为O(m), 最大和次大的元素值通过指针变量带回,函数不需要返回值; ⑷将链表中所有值比key(值key通过形参传入)小的结点作为值为key的结 点前驱,所有值比key大的结点作为值为key的结点后继,并尽量保持原有结点之间的顺序,要求该算法的时间复杂度为O(m); ⑸设计一个菜单,具有上述处理要求和退出系统功能。 ⒈本人完成的工作: 一、定义结构体:LNode 二、编写以下函数: (1)建立单循环链表 (2)建立定位查找函数 (3)求出链表中最大和次大值 (4)将链表中的值和输入的Key比较,小的作为key前驱结点,大的作为key 的后继结点 三、设计具有上述处理要求和退出系统菜单 ⒉所采用的数据结构:单链表 数据结构的定义: typedef struct Node //定义结点的结构体 { DataType data; //数据域 struct Node *next; //指针域

}LNode; //结点的类型 ⒊所设计的函数 (1)Create(void) LNode *Create(void) //建立单循环链表,链表头结点head作为返回值{ int i,j,n,A[M]; //建立数组A【M】 LNode *head,*p,*move; head=(LNode*)malloc(sizeof(LNode)); //创建空单循环链表head->next=head; move=head; printf("请输入数组元素的个数:"); //输入数组 scanf("%d",&n); printf("请输入数组:"); for(i=0;idata=A[j]; p->next=move->next; move->next=p; move=move->next; } return head; //返回头指针

数据结构课程设计题目

“数据结构”课程设计题目 1、城市链表(3) [问题描述] 将若干城市的信息,存入一个带头结点的单链表。结点中的城市信息包括:城市名,城市的位置坐标。要求能够利用城市名和位置坐标进行有关查找、插入、删除、更新等操作。 [基本要求] (1)给定一个城市名,返回其位置坐标; (2)给定一个位置坐标P和一个距离D,返回所有与P的距离小于等于D的城市。 [测试数据] 由学生依据软件工程的测试技术自己确定。注意测试边界数据。 2、约瑟夫生死者游戏(3) [问题描述] 约瑟夫(Joeph)问题的一种描述是:编号为1,2,…,n的n个人按顺时针方向围坐一圈,每人持有一个密码(正整数)。一开始任选一个正整数作为报数上限值m,从第一个人开始按顺时针方向自1开始顺序报数,报到m时停止报数。报m的人出列,将他的密码作为新的m值,从他在顺时针方向上的下一个人开始重新从1报数,如此下去,直至所有人全部出列为止。试设计一个程序求出出列顺序。 [基本要求] 利用单向循环链表存储结构模拟此过程,按照出列的顺序印出各人的编号。 [测试数据] m的初值为20;密码:3,1,7,2,4,8,4(正确的结果应为6,1,4,7,2,3,5)。 [实现提示] 程序运行后首先要求用户指定初始报数上限值,然后读取各人的密码。设n≤30。 [选作内容] 向上述程序中添加在顺序结构上实现的部分。 3、括号匹配的检验(3) [问题描述] 假设表达式中允许有两种括号:圆括号和方括号,其嵌套的顺序随意,即(()[ ])或[([ ] [ ])]等为正确格式,[( ])或(((]均为不正确的格式。检验括号是否匹配的方法可用“期待的紧迫程度”这个概念来描述。例如:考虑下列的括号序列:

数据结构(C语言)单链表的基本操作

实验名称:实验一单链表的基本操作 实验目的 熟练掌握线性表两类存储结构的描述方法。 实验内容 从键盘读入若干个整数,建一个整数单链表,并完成下列操作: (1)打印该链表; (2)在链表中插入一个结点,结点的数据域从键盘读入,打印该链表; (3)在链表中删除一个结点,被删结点的位置从键盘读入,打印该链表; (4)在链表中做查找:从键盘读入要查找的整数,将该整数在链表中的位置打印出来,若要查找的整数不在链表中,返回一个信息。 算法设计分析 (一)数据结构的定义 单链表存储结构定义为: struct Node; typedef struct Node * pnode; struct Node { int info; pnode link; }; typedef struct Node * LinkList; (二)总体设计 程序由主函数、创建单链表函数、链表长度函数、链表打印函数、插入正整数函数、删除函数、查询函数组成。其功能描述如下: (1)主函数:调用各个函数以实现相应功能 int main(void) //主函数 { printf("单链表的基本操作实验:\n"); struct list *pnode; pnode = creat(); //创建 print(pnode); //输出 insert(pnode); //插入 print(pnode); //输出 _delete(pnode); //删除 print(pnode); //输出 _located(pnode); //查找 print(pnode); //输出 return 0 ; } (三)各函数的详细设计: Function1: struct list *creat()//创建链表;

数据结构课程设计题

“数据结构”课程设计题目 1、城市链表 [问题描述] 将若干城市的信息,存入一个带头结点的单链表。结点中的城市信息包括:城市名,城市的位置坐标。要求能够利用城市名和位置坐标进行有关查找、插入、删除、更新等操作。 [基本要求] (1)给定一个城市名,返回其位置坐标; (2)给定一个位置坐标P和一个距离D,返回所有与P的距离小于等于D的城市。 [测试数据] 由学生依据软件工程的测试技术自己确定。注意测试边界数据。 2、约瑟夫生死者游戏 [问题描述] 约瑟夫(Joeph)问题的一种描述是:编号为1,2,…,n的n个人按顺时针方向围坐一圈,每人持有一个密码(正整数)。一开始任选一个正整数作为报数上限值m,从第一个人开始按顺时针方向自1开始顺序报数,报到m时停止报数。报m的人出列,将他的密码作为新的m值,从他在顺时针方向上的下一个人开始重新从1报数,如此下去,直至所有人全部出列为止。试设计一个程序求出出列顺序。 [基本要求] 利用单向循环链表存储结构模拟此过程,按照出列的顺序印出各人的编号。 [测试数据] m的初值为20;密码:3,1,7,2,4,8,4(正确的结果应为6,1,4,7,2,3,5)。 [实现提示] 程序运行后首先要求用户指定初始报数上限值,然后读取各人的密码。设n≤30。 [选作内容] 向上述程序中添加在顺序结构上实现的部分。 3、括号匹配的检验 [问题描述] 假设表达式中允许有两种括号:圆括号和方括号,其嵌套的顺序随意,即(()[ ])或[([ ] [ ])]等为正确格式,[( ])或(((]均为不正确的格式。检验括号是否匹配的方法可用“期待的紧迫程度”这个概念来描述。例如:考虑下列的括号序列:

数据结构链表代码

#include typedef struct lnode{ int data; lnode *next; }lnode; void initlist(lnode *&head){ head=new lnode; head->next=NULL; }//带头结点空链表的判断条件 /*void initlistn(lnode *&head,int n){ initlist1(head); lnode *s; for(int i=0;i>s->data; s->next=head->next; head->next=s; } }//逆序*/ void initlistn(lnode *&head,int n){ initlist(head); lnode *p=head,*s; for(int i=0;i>s->data; s->next=NULL; p->next=s; p=s; } }//正序 void print(lnode *head){ lnode *p=head->next; while(p){ cout<data<<' '; p=p->next; } cout<next;j++;}

if(!p||j>i-1) return; lnode *s=new lnode; s->data=e; s->next=p->next; p->next=s; }//插入 void deletelist(lnode *&head,int i,int &e){ lnode *p=head; int j=0; while(p->next&&jnext;j++;} if(!p->next||j>i-1) return; lnode *q=p->next; e=q->data; p->next=q->next; }//删除 void main(void){ lnode *head; initlistn(head,10); print(head); inserlist(head,6,200); print(head); int e; deletelist(head,8,e); print(head); }

数据结构与算法问题分析与源代码之单链表

单链表 1 题目编写一个程序,实现链表的各种基本运算,包括:链表操作:初始化链表、输出链表、输出链表长度和释放链表链表元素操作:插入元素、删除元素、输出元素(注意元素的位置) 2 目标熟悉单链表的定义及其基本操作的实现 3 设计思想 链表由多个结点通过next 指针连接成一个完整的数据结构,每个几点包括一个数据域和一个指向下一个结点的next 指针。通过对指针的改写与结点的增减,我们可以实现单链表的插入、删除、输入、输出、求长等操作。 4 算法描述 (1 )初始化链表:输入元素个数n ,分配n 个结点空间,输入元素值,按元素顺序初始化next 指针,使之连接成串,尾指针赋值NULL 。 (2 )输出链表:从表头开始沿next 指针遍历各结点,每次访问结点输出结点数据值,直至next 为空。 (3 )输出链表长度:从表头开始沿next 指针遍历各结点,每次访问结点计数器加一,直至next 为空,返回计数器值。 (4 )释放链表:沿next 指针从前向后依次释放结点,直至next 指空。 (5 )插入元素:指针沿next 指向移动指定位,新分配一个空间并存入数据,其next 赋值为当前指针指向结点的next ,修改当前指针指向结点的next 指向新加结点。 (6 )删除元素:指针沿next 指向移动指定位,修改待删结点的前一结点的next 指针指向待删结点的下一结点,保存数值,释放删除结点。 (7 )输出元素:指针沿next 指向移动指定位,指针指向结点数据区,读出数值返回。 5 程序结构图 6源程序 #i nclude

#i nclude typedef struct LNode { int data; struct LNode *n ext; }LNode,*Li nkList; Lin kList Ini tList_Li nk(L in kList L) { L=(L in kList)malloc(sizeof(LNode)); L->data = 0; L->next = NULL; return L; } void Createlist(L in kList L) { int n; int i; int temp; LinkList T; printf(" 输入链表元素个数:"); scanf("%d",&n); L->data=n; printf(" 输入元素值:\n"); T=L; for (i=n;i>0;i--) { LinkList p=(LinkList)malloc(sizeof(LNode)); scanf("%d",&temp); p->next=T->next; p->data = temp; T->next=p; T=p; L->data++; } printf(" 成功建立链表"); } void DestroyList_Link(LinkList L) { LinkList p = L,q = L; while(p) { p = p->next; free(q);

城市链表系统C语言数据结构

#include //其它说明// #include //I/O函数// #include //字符串函数// #include //使用malloc函数// #include //包含windowsAPI的函数声明和宏// struct CITYLIST{ //为了方便插入与删除操作,采用链式结构存储城市节点,节点定义如下: char cityName[30]; float x; //横坐标 float y; //纵坐标 float population; //城市人口// float arer; //城市面积// struct CITYLIST *Next; }; typedef struct CITYLIST cityList; void Init(cityList *LHead); //创建城市链表// void Insert(cityList *LHead); //插入新城市信息// void Delete(cityList *LHead); //删除城市信息// void Create(cityList *LHead); //退出// void FindCity(cityList* LHead); //根据城市名查询城市// void FindCityDistance(cityList* LHead); //根据离中心坐标距离查询城市// void UpdateCity(cityList* LHead); //更新城市信息// int main(int argc, char* argv[]) { system("color 3e"); //系统界面颜色设置// MessageBoxA(0,"欢迎进入城市链表系统","确定",MB_OK); //弹跳窗口设置// cityList* LHead; cityList* Store; char choice[3] = {1,2,3}; LHead = (cityList*)malloc(sizeof(cityList)); Init(LHead); Store = LHead; while(strcmp(choice,"7")){ printf(" ************************************************************************* \n"); //系统界面// printf(" ************************************************************************* \n");

数据结构双向链表实战应用(c语言源程序)

#include #include typedef struct nodes { char data; struct nodes *front; struct nodes *next; }*LinkList; int main(void) { int i=0; LinkList head_1=0,head_2=0; LinkList InitList(void);//创建不带头接点的双链表 void OutPutList(LinkList head); LinkList ChangeList(LinkList head,int m);//假如head指向abcde,如输入2,cdeab,如输入-2,则为deabc void FreeList(LinkList head); head_1=InitList(); OutPutList(head_1); printf("请输入想要移动的位数i\n"); scanf("%d",&i); head_2=ChangeList(head_1,i); OutPutList(head_2); FreeList(head_1); return 0;

} LinkList InitList(void) { int i=1; char ch;//判断是否还输入 LinkList head=0,r,t;//r指向新创建的结点,t指向r的前一个结点 head=(struct nodes *)malloc(sizeof(struct nodes)); if(!head) { printf("存储空间分配失败\n"); return 0; } head->front=head; head->next=head; head->data='a'; t=r=head; while(1) { r=(struct nodes *)malloc(sizeof(struct nodes)); if(!r) { printf("存储空间分配失败\n"); return 0; }

数据结构C语言版 循环链表表示和实现

数据结构C语言版循环链表表示和实现.txt37真诚是美酒,年份越久越醇香浓烈;真诚是焰火,在高处绽放才愈显美丽;真诚是鲜花,送之于人,手有余香。/* 数据结构C语言版循环链表表示和实现 P35 编译环境:Dev-C++ 4.9.9.2 日期:2011年2月10日 */ #include #include #include typedef int ElemType; // 线性表的单链表存储结构 typedef struct LNode { ElemType data; struct LNode *next; }LNode, *LinkList; // 要好好区分什么是头结点((*L)->next),尾结点(*L),以及第一个结 // 点(*L)->next->next,设立尾指针的单循环链表(头尾相接,即头结点 // 与尾结点是一样的,它们都没数据域. // 构造一个空的循环链表L int InitList_CL(LinkList *L) { // 产生头结点,并使L指向此头结点 *L = (LinkList)malloc(sizeof(struct LNode)); if(!*L) exit(0); // 指针域指向头结点,这样就构成了一个循环,空表循环,*L为表尾 (*L)->next = *L; return 1; } // 销毁循环链表L int DestroyList_CL(LinkList *L) { LinkList q, p = (*L)->next; // p指向头结点 while(p != *L) // 没到表尾,*L为表尾 { q = p->next; free(p);

链表的基本操作-数据结构实验报告

大学数据结构实验报告 课程名称数据结构实验第(四)次实验实验名称链表的基本操作 学生姓名于歌专业班级学号 实验成绩指导老师(签名)日期2018年10月01日 一、实验目的 1. 学会定义单链表的结点类型,实现对单链表的一些基本操作和具体 的函数定义,了解并掌握单链表的类定义以及成员函数的定义与调用。 2. 掌握单链表基本操作及两个有序表归并、单链表逆置等操作的实现。 二、实验要求 1.预习C语言中结构体的定义与基本操作方法。 2.对单链表的每个基本操作用单独的函数实现。 3.编写完整程序完成下面的实验内容并上机运行。 4.整理并上交实验报告。 三、实验内容: 1.编写程序完成单链表的下列基本操作: (1)初始化单链表La (2)在La中插入一个新结点 (3)删除La中的某一个结点 (4)在La中查找某结点并返回其位置 (5)打印输出La中的结点元素值 (6)清空链表 (7)销毁链表 2 .构造两个带有表头结点的有序单链表La、Lb,编写程序实现将La、 Lb合并成一个有序单链表Lc。 四、思考与提高: 1.如果上面实验内容2中合并的表内不允许有重复的数据该如何操作? 2.如何将一个带头结点的单链表La分解成两个同样结构的单链表Lb,Lc,使得Lb中只含La表中奇数结点,Lc中含有La表的偶数结点?五、实验设计 1.编写程序完成单链表的下列基本操作: (1)初始化单链表La LinkList InitList() {

int i,value,n; LinkList H=(LinkList)malloc(sizeof(LNode)); LinkList P=H; P->next=NULL; do{ printf("请输入链表的长度:"); scanf("%d",&n); if(n<=0) printf("输入有误请重新输入!\n"); }while(n<=0); printf("请输入各个元素:\n"); for(i=0; idata=value; P->next=NEW; NEW->next=NULL; P=NEW; } printf("链表建立成功!\n"); return H->next; } (2)在La中插入一个新结点 LinkList InsertList(LinkList L,int i,ElemType value) { LinkList h,q,t=NewLNode(t,value); int x=0; h=q=L; if(i==1) t->next=h, h=t; else { while(x++next; t->next=q->next; q->next=t; } printf("插入成功!\n"); return h; } (3)删除La中的某一个结点

数据结构实验 链表

实验名称:链表 班级:学号___________姓名:报告日期: 一、实验目的及要求 1. 掌握单链表的存储结构形式及其描述。 2. 掌握单链表的建立、查找、插入和删除操作。 二、实验内容 1. 编写函数,实现随机产生或键盘输入一组元素,建立一个带头结点的单链表(无序)。 2. 编写函数,实现遍历单链表。 3. 编写函数,实现把单向链表中元素逆置(不允许申请新的结点空间)。 4. 编写函数,建立一个非递减有序单链表。 5. 编写函数,利用以上算法,建立两个非递减有序单链表,然后合并成一个非递减链表。 6. 编写函数,在非递减有序单链表中插入一个元素使链表仍然有序。 7. 编写函数,实现在非递减有序链表中删除值为x的结点。 8. 编写一个主函数,在主函数中设计一个简单的菜单,分别调试上述算法。 三、实验结果

四、实验总结: 这次实验使我在已经掌握单链表的存储结构,单链表的建立、查找、插入和删除操作的思想的基础上,可以对其利用C语言进行编程的实现,不仅对单链表的有关内容有了更深的理解,同时也对C语言编程的学习有了很大的进步。期间也遇到不少麻烦,;例如在编好程序后,编译运行时出现很多错误,但是在同学和网络的帮助下,将其成功解决。此外,需要注意的就是在用C语言进行编程时,一定要细心,注意基础知识的积累。同时算法思想也很重要。 源代码: #include #include typedef int ElemType;

typedef struct LNode { ElemType data; struct LNode *next; }LNode,*Linklist; void Createlist(Linklist &L) { Linklist p,s; ElemType x; L=(Linklist)malloc(sizeof(LNode)); L->next=NULL; p=L; scanf("%d",&x); while(x) { s=(Linklist)malloc(sizeof(LNode)); s->data=x; s->next=NULL; p->next=s; p=s; scanf("%d",&x);} } void printlist(Linklist &L) { Linklist p; p=L; while(p->next!=NULL){ p=p->next; printf("%d ",p->data);} printf("\n"); } void nizhi(Linklist &L) { Linklist p,s; p=L->next; L->next=NULL; while(p) { s=p; p=p->next; s->next=L->next; L->next=s;} } void charu(Linklist &L,ElemType x)

数据结构课程设计单链表

目录 1 选题背景 (1) 2 方案与论证 (2) 2.1 链表的概念和作用 (2) 2.3 算法的设计思想 (3) 2.4 相关图例 (4) 2.4.1 单链表的结点结构 (4) 2.4.2 算法流程图 (4) 3 实验结果 (5) 3.1 链表的建立 (5) 3.2 单链表的插入 (5) 3.3 单链表的输出 (6) 3.4 查找元素 (6) 3.5 单链表的删除 (7) 3.6 显示链表中的元素个数(计数) (8) 4 结果分析 (9) 4.1 单链表的结构 (9) 4.2 单链表的操作特点 (9) 4.2.1 顺链操作技术 (9) 4.2.2 指针保留技术 (9) 4.3 链表处理中的相关技术 (9) 5 设计体会及今后的改进意见 (10) 参考文献 (11) 附录代码: (12)

1 选题背景 陈火旺院士把计算机60多年的发展成就概括为五个“一”:开辟一个新时代----信息时代,形成一个新产业----信息产业,产生一个新科学----计算机科学与技术,开创一种新的科研方法----计算方法,开辟一种新文化----计算机文化,这一概括深刻影响了计算机对社会发展所产生的广泛而深远的影响。 数据结构和算法是计算机求解问题过程的两大基石。著名的计算机科学家P.Wegner指出,“在工业革命中其核心作用的是能量,而在计算机革命中其核心作用的是信息”。计算机科学就是“一种关于信息结构转换的科学”。信息结构(数据结构)是计算机科学研究的基本课题,数据结构又是算法研究的基础。

2 方案与论证 2.1 链表的概念和作用 链表是一种链式存储结构,链表属于线性表,采用链式存储结构,也是常用的动态存储方法。链表中的数据是以结点来表示的,每个结点的构成:元素(数据元素的映象) + 指针(指示后继元素存储位置),元素就是存储数据的存储单元,指针就是连接每个结点的地址数据。 以“结点的序列”表示线性表称作线性链表(单链表) 单链表是链式存取的结构,为找第 i 个数据元素,必须先找到第 i-1 个数据元素。 因此,查找第 i 个数据元素的基本操作为:移动指针,比较 j 和 i 单链表 1、链接存储方法 链接方式存储的线性表简称为链表(Linked List)。 链表的具体存储表示为: ① 用一组任意的存储单元来存放线性表的结点(这组存储单元既可以是连续的,也可以是不连续的) ② 链表中结点的逻辑次序和物理次序不一定相同。为了能正确表示结点间的逻辑关系,在存储每个结点值的同时,还必须存储指示其后继结点的地址(或位置)信息(称为指针(pointer)或链(link)) 注意: 链式存储是最常用的存储方式之一,它不仅可用来表示线性表,而且可用来表示各种非线性的数据结构。 2、链表的结点结构 ┌───┬───┐ │data │next │ └───┴───┘ data域--存放结点值的数据域 next域--存放结点的直接后继的地址(位置)的指针域(链域) 注意: ①链表通过每个结点的链域将线性表的n个结点按其逻辑顺序链接在一起的。 ②每个结点只有一个链域的链表称为单链表(Single Linked List)。

相关主题
相关文档 最新文档