数据结构第2章 链表 练习题

1.1. 一元稀疏多项式的求导算法

写出一元稀疏多项式的求导算法，用带表头结点的单链表存储该一元稀疏多项式，Lb为头指针，用类C语言描述该求导算法，不另行开辟存储空间，删除无用结点，并分析算法的时间复杂度。该链表的数据结构如下：

typedef struct LNode{

float coe; //系数

int exp; //指数

struct LNode *next; //指针

} LNode , *LinkList ;

求导算法如下：

void Differential(LinkList &Lb)

{ //求导算法

pre=Lb; p=pre->next;

while ( p )

{

if ( p->exp != 0 )//指数不等于零

{

p->coe = p->coe * p->exp ;

p->exp = p->exp – 1 ;

pre = pre->next ;

}

else//指数等于零

{

pre->next = p->next ;

free ( p );

}

p = pre->next ;

}

}

时间复杂度为: O(n)

1.2. 单链表存储结构的排序算法

排序算法：将一组整数排序成非递减有序序列。用带头结点的单链表存储，L为头指针，用类C语言写出该排序算法，不另行开辟存储空间，并分析算法的时间复杂度。该单链表的数据结构如下：

typedef struct LNode{

int data; //数据域

struct LNode *next; //指针域

} LNode , *LinkList ;

void Sort(LinkList &L)

{ //排序算法如下：将L排序成非递减单链表

q=L; p=q->next->next; q->next->next=NULL;

while(p)

{

While(q->next && p->data >= q->next->data)

q=q->next;

s=p->next;

p->next=q->next;

q->next=p;

p=s;

q=L;

}

}//sort

1.3. 设H为具有n(n>0，n很大且未知)个数据元素的单链表的头结点指针，试采用C语言编写一个程序，完成将单链表中第n/2个数据元素之后的全部数据元素倒置的功能。要求不另行开辟存储空间，算法的时间复杂度不超过O(n)。

单链表结点的数据类型描述如下：

typedef struct Lnode {

int data; //数据元素为整数

struct Lnode *next;

}Lnode, *LinkList;

void ReverseN2(LinkList &H)

{//将单链表的正中间位置结点之后的全部结点倒置的功能

LinkList p,q,s;

p=H;

q=H;

//定位链表正中间位置结点。p结点走到表尾，q结点在正中间位置while (p)

{ if (p->next) //如果不是表尾结点，就走二步

p=p->next->next;

else//如果是表尾结点，就走一步

{p=p->next; break;}

q=q->next;

}

//将单链表的正中间位置结点之后的全部结点倒置的功能

p=q->next; q->next=NULL;

while (p)

{ s=p->next;

p->next=q->next;

q->next=p;

p=s;

}

}//ReverseN2

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

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

#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

(完整版)数据结构实验报告全集

数据结构实验报告全集 实验一线性表基本操作和简单程序 1 ．实验目的 （1 ）掌握使用Visual C++ 6.0 上机调试程序的基本方法； （2 ）掌握线性表的基本操作：初始化、插入、删除、取数据元素等运算在顺序存储结构和链表存储结构上的程序设计方法。 2 ．实验要求 （1 ）认真阅读和掌握和本实验相关的教材内容。 （2 ）认真阅读和掌握本章相关内容的程序。 （3 ）上机运行程序。 （4 ）保存和打印出程序的运行结果，并结合程序进行分析。 （5 ）按照你对线性表的操作需要，重新改写主程序并运行，打印出文件清单和运行结果 实验代码： 1）头文件模块 #include iostream.h>// 头文件 #include// 库头文件------ 动态分配内存空间 typedef int elemtype;// 定义数据域的类型 typedef struct linknode// 定义结点类型 { elemtype data;// 定义数据域 struct linknode *next;// 定义结点指针 }nodetype; 2）创建单链表

nodetype *create()// 建立单链表，由用户输入各结点data 域之值， // 以0 表示输入结束 { elemtype d;// 定义数据元素d nodetype *h=NULL,*s,*t;// 定义结点指针 int i=1; cout<<" 建立一个单链表"<> d; if(d==0) break;// 以0 表示输入结束 if(i==1)// 建立第一个结点 { h=(nodetype*)malloc(sizeof(nodetype));// 表示指针h h->data=d;h->next=NULL;t=h;//h 是头指针 } else// 建立其余结点 { s=(nodetype*) malloc(sizeof(nodetype)); s->data=d;s->next=NULL;t->next=s; t=s;//t 始终指向生成的单链表的最后一个节点

数据结构习题及答案精编版

第一章 1．在数据结构中，从逻辑上可以把数据结构分为（C ） A．动态结构和静态结构 B. 紧凑结构和非紧凑结构 C．线性结构和非线性结构 D. 内部结构和外部结构 ● 2.在数据结构中,与所使用的计算机无关的是( A ) A. 逻辑结构 B. 存储结构 C. 逻辑和存储结构 D. 物理结构 3.下面程序的时间复杂度为____O（mn）_______。 for (int i=1; i<=m; i++) for (int j=1; j<=n; j++ ) S+=i 第二章线性表 ●链表不具备的特点是（A） A 可以随机访问任一结点（顺序） B 插入删除不需要移动元素 C 不必事先估计空间 D 所需空间与其长度成正比 2. 不带头结点的单链表head为空的判定条件为（A ），带头结点的单链表head为空的判定条件为（B ） A head==null B head->next==null C head->next==head D head!=null ●3.在线性表的下列存储结构中，读取元素花费时间最少的是（D） A 单链表 B 双链表 C 循环链表 D 顺序表 ● 4.对于只在表的首、尾两端进行手稿操作的线性表，宜采用的存储结构为(C) A 顺序表 B 用头指针表示的单循环链表 C 用尾指针表示的单循环链表 D 单链表 ● 5.在一个具有n 个结点的有序单链表中插入一个新的结点，并保持链表元素仍然有序， 则操作的时间复杂度为( D ) A O(1) B O(log2n) C O(n2) D O(n) ● 6.在一个长度为n (n>1)的单链表上，设有头和尾两个指针，执行(B)操作与链表的长 度有关 A 删除单链表中第一个元素 B 删除单链表中最后一个元素 C 在第一个元素之前插入一个新元素 D 在最后一个元素之后插入一个新元素 ●7.与单链表相比，双向链表的优点之一是(D) A 插入删除操作更简单 B 可以进行随机访问 C 可以省略表头指针或表尾指针 D 顺序访问相邻结点更容易 ●8.若list是某带头结点的循环链表的头结点指针，则该链表最后那个链结点的指针域 (头结点的地址)中存放的是( B ) A list的地址 B list的内容 C list指的链结点的值 D 链表第一个链结点的地址 ●9.若list1和list2分别为一个单链表与一个双向链表的第一个结点的指针，则( B ) A list2比list1占用更多的存储单元 B list1与list2占用相同的存储单元 C list1和list2应该是相同类型的指针变量 D 双向链表比单链表占用更多的存储单元 10.链表中的每个链结点占用的存储空间不必连续，这句话正确吗？ (不正确) 11. 某线性表采用顺序存储结构，元素长度为4，首地址为100，则下标为12的（第13个）元素的存储地址为148。V 100+4*12=148 11.在顺序表的（最后一个结点之后）插入一个新的数据元素不必移动任何元素。 12.若对线性表进行的操作主要不是插入删除，则该线性表宜采用（顺序）存储结构，若频繁地对线性表进行插入和删除操作，则该线性表宜采用( 链 )存储结构。

数据结构 单链表详解

数据结构的概念： 数据的逻辑结构+ 数据的存储结构+ 数据的操作； 数据的数值：=====》数据===》数值型数据整形浮点数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};

数据结构实验报告

数据结构实验报告 一．题目要求 1）编程实现二叉排序树，包括生成、插入，删除； 2）对二叉排序树进行先根、中根、和后根非递归遍历； 3）每次对树的修改操作和遍历操作的显示结果都需要在屏幕上用树的形状表示出来。 4）分别用二叉排序树和数组去存储一个班(50人以上)的成员信息(至少包括学号、姓名、成绩3项),对比查找效率，并说明在什么情况下二叉排序树效率高,为什么? 二．解决方案 对于前三个题目要求，我们用一个程序实现代码如下 #include #include #include #include "Stack.h"//栈的头文件，没有用上 typedefintElemType; //数据类型 typedefint Status; //返回值类型 //定义二叉树结构 typedefstructBiTNode{ ElemType data; //数据域 structBiTNode *lChild, *rChild;//左右子树域 }BiTNode, *BiTree; intInsertBST(BiTree&T,int key){//插入二叉树函数 if(T==NULL) { T = (BiTree)malloc(sizeof(BiTNode)); T->data=key; T->lChild=T->rChild=NULL; return 1; } else if(keydata){ InsertBST(T->lChild,key); } else if(key>T->data){ InsertBST(T->rChild,key); } else return 0; } BiTreeCreateBST(int a[],int n){//创建二叉树函数 BiTreebst=NULL; inti=0; while(i

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

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

实现要求： ⑴单链表建立函数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 选题背景 (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）。

数据结构实验报告图实验

图实验一，邻接矩阵的实现 1.实验目的 （1）掌握图的逻辑结构 （2）掌握图的邻接矩阵的存储结构 （3）验证图的邻接矩阵存储及其遍历操作的实现 2.实验内容 （1）建立无向图的邻接矩阵存储 （2）进行深度优先遍历 （3）进行广度优先遍历 3．设计与编码 MGraph.h #ifndef MGraph_H #define MGraph_H const int MaxSize = 10;

template class MGraph { public: MGraph(DataType a[], int n, int e); ~MGraph(){ } void DFSTraverse(int v); void BFSTraverse(int v); private: DataType vertex[MaxSize]; int arc[MaxSize][MaxSize]; int vertexNum, arcNum; }; #endif MGraph.cpp

#include using namespace std; #include "MGraph.h" extern int visited[MaxSize]; template MGraph::MGraph(DataType a[], int n, int e) { int i, j, k; vertexNum = n, arcNum = e; for(i = 0; i < vertexNum; i++) vertex[i] = a[i]; for(i = 0;i < vertexNum; i++) for(j = 0; j < vertexNum; j++) arc[i][j] = 0; for(k = 0; k < arcNum; k++) {

数据结构(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()//创建链表；

数据结构实验报告2

数据结构实验报告 二．程序设计相关信息 （1）实验题目：编写一个程序algo2-3.cpp，实现双链表的各种基本运算，并在此基础上设计一个主程序完成如下功能： 1.初始化双链表h； 2.依次采用尾插法插入a，b，c，d，e元素； 3.输出双链表h； 4.输出双链表h长度； 5.输出双链表h是否为空； 6.判断双链表h的第3个元素； 7.输出元素‘a’的位置； 8.在第4个元素位置上插入‘f’元素； 9.输出双链表h； 10.删除L的第3个元素； 11.输出双链表h； 12.释放双链表h。 （2）实验目的：熟悉双链表的基本操作并掌握尾插法建表。 （3）算法描述或流程图

(4)源代码 #include #include

typedef struct DNode { char data; struct DNode *next; struct DNode *prior; }DNode,DLinkList; void initlist(DLinkList *&h) { h=(DLinkList*)malloc(sizeof(DLinkList)) ; h->next=NULL; h->prior=NULL; } void destroylist(DLinkList *&h) { DLinkList *p=h,*q=p->next; while(q!=NULL) {free(p); p=q; q=p->next; } free(p); } int getelem(DLinkList *h,int i,char &e) {int j=0; DLinkList *p=h; while(jnext; } if(p==NULL) return 0; else { e=p->data; return 1; } } int listempty(DLinkList *h) { return(h->next==NULL&&h->prior==NULL); } int listlength(DLinkList *h) { DLinkList *p=h;int n=0; while(p->next!=NULL) {n++; p=p->next; } return (n);

数据结构链表代码

#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 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);

《数据结构》实验报告

《数据结构》实验报告 实验序号：4 实验项目名称：栈的操作

附源程序清单： 1. #include #define MaxSize 100 using namespace std; typedef int ElemType; typedef struct { ElemType data[MaxSize]; int top; }SqStack; void InitStack(SqStack *st) //初始化栈 { st->top=-1; } int StackEmpty(SqStack *st) //判断栈为空{ return (st->top==-1); } bool Push(SqStack *st,ElemType x) //元素进栈{ if(st->top==MaxSize-1)

{ return false; } else { st->top++; //移动栈顶位置 st->data[st->top]=x; //元素进栈 } return true; } bool Pop(SqStack *st,ElemType &e) //出栈 { if(st->top==-1) { return false; } else { e=st->data[st->top]; //元素出栈 st->top--; //移动栈顶位置} return true; } //函数名：Pushs //功能：数组入栈 //参数：st栈名,a->数组名，i->数组个数 bool Pushs(SqStack *st,ElemType *a,int i) { int n=0; for(;n数组名，i->数组个数 bool Pops(SqStack *st,ElemType *a,int i) { int n=0; for(;n

数据结构实验 链表

实验名称：链表 班级：学号___________姓名：报告日期： 一、实验目的及要求 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）。

数据结构实验报告

本科实验报告 课程名称：数据结构（C语言版） 实验项目：线性表、树、图、查找、内排序实验地点：明向校区实验楼208 专业班级：学号： 学生姓名： 指导教师：杨永强 2019 年 1 月10日

#include #include #include #define OK 1 typedef struct{//项的表示，多项式的项作为LinkList的数据元素float coef;//系数 int expn;//指数 }term,ElemType; typedef struct LNode{ //单链表节点结构 ElemType data; struct LNode *next; }LNode, *LinkList; typedef LinkList polynomial; int CreatLinkList(polynomial &P,int n){ //创建多项式P = (polynomial)malloc(sizeof(LNode)); polynomial q=P; q->next=NULL; polynomial s; for(int i = 0; i < n; i++){ s = (polynomial)malloc(sizeof(LNode)); scanf("%f%d",&(s->data.coef),&(s->data.expn)); q->next = s; s->next = NULL; q=q->next; } return OK; } 运行结果 2. void PrintfPolyn(polynomial P){ polynomial q; for(q=P->next;q;q=q->next){ if(q->data.coef!=1) printf("%g",q->data.coef);