假设有一个循环链表的长度大于1,且表中既无头结点也无头指针。已知S为指向链表某个结点的指针(C语言)
#include
#include
typedef struct _DLNode
{
struct _DLNode *next;
int value;
} DLNode;
/*
* 1. 如果链有没有节点，就返回NULL
* 2. 如果链表只有一个节点，输入节点的前驱节点就是它本身，则返回输入节点* 3. 如果链表有多于一个节点，就返回输入节点的前驱节点
*/
DLNode* getPriorNode(DLNode *node)
{
DLNode *next;
if (!node)
{
return NULL;
}
next = node->next;
while (node != next->next)
{
next = next->next;
}
return next;
}
void delPriorNode(DLNode *node)
{
DLNode *prior = getPriorNode(node);
if (prior)
{
getPriorNode(prior)->next = prior->next;
/* free(prior); */ /* 只有节点是malloc的才能free */
}
}
void printList(DLNode *node)
{
DLNode *next;
if (!node)
{
return;
}
printf("%d", node->value);
next = node->next;
while (node != next)
{
printf("-->%d", next->value);
next = next->next;
}
printf("\n");
}
void main()
{
DLNode n1, n2, n3, n4, n5, n6;
n1.value = 1;
n2.value = 2;
n3.value = 3;
n4.value = 4;
n5.value = 5;
n6.value = 6;
n1.next = &n2;
n2.next = &n3;
n3.next = &n4;
n4.next = &n5;
n5.next = &n6;
n6.next = &n1;
printf("Original list: ");
printList(&n1);
delPriorNode(&n3);
printf("Deleted node third prior node(node 2): "); printList(&n1);
}
c语言链表解析
c语言链表解析 编程思想： 链表由一系列不必在内存中相连的结构组成。每一个结构均含有表元素和指向包含该元素后继元的结构指针。我们称之为next指针。最后一个单元的next指针指向NULL；该值由C定义并且不能与其它指针混淆。ANSI C规定NULL为零。 指针变量是包含存储另外某个数据的地址的变量。因此，如果P被声明为指向一个结构的指针，那么存储在P中的值就被解释为内存中的一个位置，在该位置能够找到一个结构。该结构的一个域可以通过P->FileName访问，其中FileName是我们要考察的域的名字。如图1所示，这个表含有五个结构，恰好在内存中分配给它们的位置分别是1000，800,712,992和692。第一个结构的指针含有值800，它提供了第二个结构所在的位置。其余每个结构也都有一个指针用于类似的目的。当然，为了访问该表，我们需要知道在哪里能够找到第一个单元。 图1 为了执行打印表PrinList（L）或查找表Find（L，key），只要将一个指针传递到该表的第一个元素，然后用一些Next指针穿越该表即可。 删除命令可以通过修改一个指针来实现。图2给出在原表中删除第三个元素的结果。 图2 插入命令需要使用一次malloc调用从系统得到一个新单元并在此后执行两次指针调整。想法通过图3给出，其中虚线表示原来的指针。 图3
程序设计： 上面的描述实际上足以使每一部分都能正常工作，但还是有几处地方可能会出问题： 1、并不存在从所给定义出发在表的前面插入元素的真正显性的方法。 2、从表的前面实行删除是一个特殊情况，因为它改变了表的起始端；编程的疏忽将会造成表的丢失。 3、在执行删除命令时，要求我们记住被删除元素前面的表元。 事实上，稍作一个简单的变化就能够解决所有这三个问题。做一个标志节点——表头（header）。图4表示一个带头头结点的链表。 图4 为了避免删除操作相关的一些问题，我们需要编写一个FindPrevious函数，它将返回我们要删除的表元的前驱元的位置。如果我们使用表头，那么当删除表的第一个元素时，FindPrevious将返回表头的位置。 代码实现： 按照C的约定，作为类型的List（表）和Position（位置）以及函数的原型都列在所谓的.h 头文件中。具体的Node（节点）声明则在.c文件中。 代码1、链表的类型声明 #ifndef _List_H struct Node; typedef struct Node *PtrToNode; typedef PtrToNode List; typedef PtrToNode Posotion; List MakeEmpty(List L); int IsEmpty(List L); int IsLast（Position P， List L）； Position Find(ElementType X, List L); void Delete(ElementType X, List L); Position FindPrevious(ElementType X, List L); void Insert(ElementType X, List L, Position P); void DeleteList(List L); struct Node { ElementType Elment; Position Next; } 代码2、测试一个链表是否是空表的函数。（头结点的Next指向NULL时为空链表）
C++链表的创建与操作
C++链表的创建与操作 我们知道，数组式计算机根据事先定义好的数组类型与长度自动为其分配一连续的存储单元，相同数组的位置和距离都是固定的，也就是说，任何一个数组元素的地址都可一个简单的公式计算出来，因此这种结构可以有效的对数组元素进行随机访问。但若对数组元素进行插入和删除操作，则会引起大量数据的移动，从而使简单的数据处理变得非常复杂，低效。 为了能有效地解决这些问题，一种称为“链表”的数据结构得到了广泛应用。 1．链表概述 链表是一种动态数据结构，他的特点是用一组任意的存储单元（可以是连续的，也可以是不连续的）存放数据元素。 链表中每一个元素成为“结点”，每一个结点都是由数据域和指针域组成的，每个结点中的指针域指向下一个结点。Head是“头指针”，表示链表的开始，用来指向第一个结点，而最后一个指针的指针域为NULL(空地址)，表示链表的结束。 可以看出链表结构必须利用指针才能实现，即一个结点中必须包含一个指针变量，用来存放下一个结点的地址。 实际上，链表中的每个结点可以用若干个数据和若干个指针。结点中只有一个指针的链表称为单链表，这是最简单的链表结构。 再c++中实现一个单链表结构比较简单。例如，可定义单链表结构的最简单形式如下 struct Node{ int Data; Node *next; }; 这里用到了结构体类型。其中，*next是指针域，用来指向该结点的下一个结点；Data是一个整形变量，用来存放结点中的数据。当然，Data可以是任何数据类型，包括结构体类型或类类型。 在此基础上，我们在定义一个链表类list，其中包含链表结点的插入，删除，输出等功能的成员函数。class list{ Node *head; public: list(){head=NULL;} void insertlist(int aDate,int bDate); //链表结点的插入 void Deletelist(int aDate); //链表结点的删除 void Outputlist(); //链表结点的输出 Node*Gethead(){return head;} }; 2．链表结点的访问 由于链表中的各个结点是由指针链接在一起的，其存储单元文笔是连续的，因此，对其中任意结点的地址无法向数组一样，用一个简单的公式计算出来，进行随机访问。只能从链表的头指针（即head）开始，用一个指针p先指向第一个结点，然后根据结点p找到下一个结点。以此类推，直至找到所要访问的结点或到最后一个结点（指针为空）为止。 下面我们给出上述链表的输出函数； void list::Outputlist(){ Node *current = head; while(current != NULL){ cout << current->Data << " "; current = current->next;
指针测试题
C++测试(指针) 学号姓名成绩 一、选择题(每题1.5分,共24分) １．语句int a=10,*point=&a；其值不为地址。 A. point B. &a C. &point D. *point ２．若p为指针变量，y为变量，则y = *p++；的含义是 A．y=*p;p++ B．y=(*p)++ C．y=p;p++ D．p++;y=*p ３．语句char str[]=?visual C++?;char *p=str;则p的值为 A. ?visual C++? B.str的首地址 C. \n D.?v? ４．设有说明语句char *s[]={?student?,?Teacher?,?Father?,?Month?}, *ps=s[2];执行语句：cout<<*s[1]<<’,’<
C语言指针实验报告
C语言程序设计实验报告 1实验目的 （1）掌握指针的概念，会定义和使用指针变量； （2）能正确使用变量的指针和指向变量的指针变量； （3）能正确使用数组的指针和指向数组的指针变量； （4）能正确使用字符串的指针和指向字符串的指针变量； 2实验内容 将一个任意整数插入到已排序的整形数组中，插入后，数组中的数仍然保持有序；要求： （1）整形数组直接由赋值的方式初始化，要插入的整数有scanf()函数数入；（2）算法实现过程采用指针进行处理； （3）输入原始数据以及插入整数后的数据，并加以说明；
3算法描述流程图
4源程序 #include
for(i=n-1;a[i]>=w;i--) { a[i+1]=a[i]; } a[i+1]=m; 这一步没有注意a[i++]=m和a[i+1]=m中i++和i+1不同，a[i++]=m是先将的值赋给a[i]，然后在执行自增；而在实验过程中忽略了这一点，造成了不必要的麻烦； 8实验心得 通过这次指针实验掌握了指针的概念，会定义和使用指针变量，并且能利用指针来简单化一些问题，给以后的编程带来了很大的便利；
C程序设计(链表)习题与答案
一、单选题 1、链表不具有的特点是（）。 A.不必事先估计存储空间 B.插入、删除不需要移动元素 C.可随机访问任一元素 D.所需空间与线性表长度成正比 正确答案：C 2、链接存储的存储结构所占存储空间（）。 A.分两部分，一部分存放结点值，另一部分存放结点所占单元数 B.只有一部分，存放结点值 C.分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针 D.只有一部分，存储表示结点间关系的指针 正确答案：C 3、链表是一种采用（）存储结构存储的线性表。 A.网状 B.星式 C.链式 D.顺序 正确答案：C 4、有以下结构体说明和变量的定义，且指针p指向变量a，指针q指向变量b，则不能把结点b连接到结点a之后的语句是（）。 struct node { char data; struct node *next; } a,b,*p=&a,*q=&b;
A.(*p).next=q; B.p.next=&b; C.a.next=q; D.p->next=&b; 正确答案：B 5、下面程序执行后的输出结果是（）。 #include
线性表练习题(答案)
第2章线性表 一选择题 下列程序段的时间复杂度为（ C ）。 for( int i=1;i<=n;i++) for( int j=1;j<= m; j++) A[i][j] = i*j ; A. O(m2) B. O(n2) C. O(m*n) D. (m+n) 下面关于线性表的叙述中，错误的是哪一个？（B ） A．线性表采用顺序存储，必须占用一片连续的存储单元。 B．线性表采用顺序存储，便于进行插入和删除操作。 C．线性表采用链接存储，不必占用一片连续的存储单元。 D．线性表采用链接存储，便于插入和删除操作。 线性表是具有n个（ C ）的有限序列（n>0）。 A．表元素B．字符C．数据元素D．数据项 若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ A ）存储方式最节省时间。 A．顺序表B．双链表C．带头结点的双循环链表D．单循环链表 某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ D ）存储方式最节省运算时间。 A．单链表B．仅有头指针的单循环链表 C．双链表D．仅有尾指针的单循环链表 设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用( D )最节省时间。A. 单链表 B.单循环链表 C. 带尾指针的单循环链表 D.带头结点的双循环链表 若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点。则采用（ D ）存储方式最节省运算时间。 A．单链表B．双链表C．单循环链表D．带头结点的双循环链表 链表不具有的特点是（ B ） A．插入、删除不需要移动元素B．可随机访问任一元素 C．不必事先估计存储空间D．所需空间与线性长度成正比 下面的叙述不正确的是（B,C ） A．线性表在链式存储时，查找第i个元素的时间同i的值成正比 B. 线性表在链式存储时，查找第i个元素的时间同i的值无关 C. 线性表在顺序存储时，查找第i个元素的时间同i 的值成正比 D. 线性表在顺序存储时，查找第i个元素的时间同i的值无关 若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（ C ）(1<=i<=n+1)。 A. O(0) B. O(1) C. O(n) D. O(n2) 对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为（C ）。 A．O(n) O(n) B. O(n) O(1) C. O(1) O(n) D. O(1) O(1) 线性表（a1,a2,…,an）以链接方式存储时，访问第i位置元素的时间复杂性为（ C ）A．O（i）B．O（1）C．O（n）D．O（i-1） 循环链表H的尾结点P的特点是（A ）。 A．P->next=H B．P->next= H->next C．P=H D．P=H->next 完成在双循环链表结点p之后插入s的操作是（D ）；
指针实验
实验名称：指针使用 实验目的：熟悉指针的正确用法。 相关知识：1.指针的定义；2.指针的引用； 实验内容： (1) 调试下面程序，指出错误原因。 main ( ) { int x=10,y=5,*px,*py; px=py; px=&x; py=&y; printf(“*px=%d,*py=%d”,*px,*py); } （2）调试下面程序。 #include
（3）调试下面程序。 #include
C语言指针实验报告
C语言程序设计实验报告 1实验目得 （1）掌握指针得概念,会定义与使用指针变量; （2）能正确使用变量得指针与指向变量得指针变量; （3）能正确使用数组得指针与指向数组得指针变量; （4）能正确使用字符串得指针与指向字符串得指针变量; 2实验内容 将一个任意整数插入到已排序得整形数组中,插入后,数组中得数仍然保持有序; 要求: （1）整形数组直接由赋值得方式初始化,要插入得整数有scanf()函数数入; （2）算法实现过程采用指针进行处理; （3）输入原始数据以及插入整数后得数据,并加以说明;
3算法描述流程图
4源程序 #include
for(i=n-1;a[i]>=w;i--) { a[i+1]=a[i]; } a[i+1]=m; 这一步没有注意a[i++]=m与a[i+1]=m中i++与i+1不同,a[i++]=m就是先将得值赋给a[i],然后在执行自增;而在实验过程中忽略了这一点,造成了不必要得麻烦; 8实验心得 通过这次指针实验掌握了指针得概念,会定义与使用指针变量,并且能利用指针来简单化一些问题,给以后得编程带来了很大得便利;
变量的指针和指针变量的区别是什么
2变量的指针和指针变量的区别是什么。 答；一个变量的地址指出了变量的存储单元在内存中的具体位置，能对变量进行存取操作。这个变量的地址就是变量的指针。指针是一种具有特殊意义的整型数，指针不能存放在一般的整型变量中，必须存放在专门指针的变量中，这类变量就是指针变量。 3 一维数组元素的引用有哪些方式。 答；下标法、地址法、指针法 4 2维数组列地址有哪些计算方法。 答；1 根据数组元素所在的行计算出行地址，然后把行地址转换成行中首元素的地址，再根据数组元素所在的列计算数组元素的地址。 2 根据2维数组的数组元素在存储空间上按行连续存放的特点，每个数组元素的地址等于2维数组元素的首元素地址加上该数组元素相对于首元素位置的偏移量。 3把2维数组的每一行当作一个一维数组，用一维数组元素地址的计算方法计算相应的2维数组元素的地址。 第9章结构体与共用体 1 什么是链表。其中单向链表具有哪些特点。 答；链表是若干个同样类型的结构通过依次串接方式构成的一种动态数据结构。链表中的每一个结构体数据成为结点，链表可以分成单向链表和双向链表 单向链表的特点；1 链表中的结点数据可以改变的 2 结点占用的内存是动态分配内存和动态释放内存函数。 2 对单向链表的常用操作有哪些。 答；对单向链表的常用操作有建立、显示、插入，删除和查找。 3 什么是共用体。 答；共用体是一个集合体。它的各个成员的数据类型可以是不相同的，所有成员共享同一段存储空间，存储空间的大小取决存储单元最大的成员的数据类型。 4 指向结构体类型变量的指针变量引用形式有哪些。 答；有两种形式；【星号指针变量名】。成员名和指针变量名-大于号成员名。 第10章位运算及编译预处理 1 C提供的编译预处理功能有哪些。如何实现。 答；功能有三种；宏定义、文件包含和条件编译，分别用宏定义命令、文件包含命令、条件编译命令实现。 2 文件包含的基本功能是什么。 答；文件包含处理是一个源文件可以将另一个源文件的全部内容包含到本文件中来，作为本文件的一部分，这可以节省程序设计人员的重复劳动。 【3【在C语言中提供了几种什么样的位运算符。 答；-、小于小于、大于大于、 4 文件包含需要注意哪些问题 答；一个井include命令只能指定一个被包含文件，包含多个文件侧需多个井include命令；文件包含可以嵌套，即一个被包含文件中可以包含另一个被包含的文件；在井include命令中，文件名可以用双引号或尖括号括起来。 第11章文件 1 文件的结束标志有哪些。 答；每个文件都有一个结束标志。当文件的位置指针移到文件的结束标志处时，表示文件结束。如何测试文件是否结束，常有2种方法 1 ASCII码文件的结束标志用【-1】表示。
C语言链表专题复习
链表专题复习 数组作为存放同类数据的集合，给我们在程序设计时带来很多的方便，增加了灵活性。但数组也同样存在一些弊病。如数组的大小在定义时要事先规定，不能在程序中进行调整，这样一来，在程序设计中针对不同问题有时需要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 ( )函数向系统申请分配一个节点。
c语言指针实验报告
C语言实习报告 题目：指针及其应用 系别： 专业： 姓名： 学号： 日期：
一实验名称：指针及其应用 二实验目的： （1）掌握变量的指针及其基本用法。 （2）掌握一维数组的指针及其基本用法。 （3）掌握指针变量作为函数的参数时，参数的传递过程及其用法。 三实验内容： （1）运行以下程序，并从中了解变量的指针和指针变量的概念。 （2）运行以下程序，观察&a[0]、&a[i]和p的变化，然后回答以下问题： 1.程序的功能是什么？ 2.在开始进入循环体之前，p指向谁？ 3.循环每增加一次，p的值（地址）增加多少？它指向谁？ 4.退出循环后，p指向谁？ 5.你是否初步掌握了通过指针变量引用数组元素的方法？ （3）先分析以下程序的运行结果，然后上机验证，并通过此例掌握通过指针变量引用数组元素的各种方法。
（4）编写函数，将n个数按原来的顺序的逆序排列（要求用指针实现），然后编写主函数完成： ①输入10个数； ②调用此函数进行重排； ③输出重排后的结果。 四分析与讨论： （1）指针的定义方法，指针和变量的关系。 定义方法： 数据类型 *指针变量名; 如定义一个指向int型变量的指针—— int *p;
则我们可以继续写如下代码—— int a = 4; p = &a; printf("%d", *p); 在这里，我们定义了一个变量a，我们把它理解为内存空间连续的4个字节（int型占用4字节），则这4个字节的空间保存着一个数4。&是取地址符号，即把变量a的地址（即这4个字节的首地址）赋给指针p （记住指针p的类型和变量a的类型要保持一致，否则的话，要进行类型转换）。这样子，指针p就保存着变量a的地址。我们如果把指针p当做内存空间里面另外一个连续的4个字节，那么这4个字节保存的数就是变量a的地址。printf("%d",*p)和printf("%d",a)的结果是一样的。这里的*是取变量符号（与&刚好作用相反，通过变量的地址找到变量），与定义时int *p的*号作用不同（定义时的*表示该变量是个 指针变量，而非是取它指向的变量）。 （2）数组和指针的关系。 指针与数组是C语言中很重要的两个概念，它们之间有着密切的关系，利用这种关系，可以增强处理数组的灵活性，加快运行速度，本文着重讨论指针与数组之间的联系及在编程中的应用。 1．指针与数组的关系 当一个指针变量被初始化成数组名时，就说该指针变量指向了数组。如： char str[20], ＊ptr; ptr=str; ptr被置为数组str的第一个元素的地址，因为数组名就是该数组的首地址，也是数组第一个元素的地址。此时可以认为指针ptr就是数组str（反之不成立），这样原来对数组的处理都可以用指针来实现。如对数组元素的访问，既可以用下标变量访问，也可以用指针访问。 2．指向数组元素的指针 若有如下定义： int a[10], ＊pa; pa=a; 则p=&a[0]是将数组第1个元素的地址赋给了指针变量p。 实际上，C语言中数组名就是数组的首地址，所以第一个元素的地址可以用两种方法获得：p=&a[0]或p=a。 这两种方法在形式上相像，其区别在于：pa是指针变量，a是数组名。值得注意的是：pa是一个可以变化的指针变量，而a是一个常数。因为数组一经被说明，数组的地址也就是固定的，因此a是不能变化的，不允许使用a＋＋、＋＋a或语句a＋=10，而pa＋＋、＋＋pa、pa＋=10则是正确的。由此可见，此时指针与数组融为一体。 3．指针与一维数组 理解指针与一维数组的关系，首先要了解在编译系统中，一维数组的存储组织形式和对数组元素的访问方法。 一维数组是一个线形表，它被存放在一片连续的内存单元中。C语言对数组的访问是通过数组名（数组的起始地址）加上相对于起始地址的相对量（由下标变量给出），得到要访问的数组元素的单元地址，然后再对计算出的单元地址的内容进行访问。通常把数据类型所占单元的字节个数称为扩大因子。 实际上编译系统将数组元素的形式a[i]转换成＊(a＋i)，然后才进行运算。对于一般数组元素的形式：<数组名>[<下标表达式>]，编译程序将其转换成：＊(<数组名>＋<下标表达式>)，其中下标表达式为：下标表达式＊扩大因子。整个式子计算结果是一个内存地址，最后的结果为：＊<地址>=<地址所对应单元的地址的内容>。由此可见，C语言对数组的处理，实际上是转换成指针地址的运算。 数组与指针暗中结合在一起。因此，任何能由下标完成的操作，都可以用指针来实现，一个不带下标的数组名就是一个指向该数组的指针。
C语言通用数据类型链表的构造数据域为指针
和一般的数据结构里面的链表的实现没什么大不同， 在list.h里面只修改一个地方 typedef void * ElemType; 也就是说数据域是一个无类型指针，链表本身不对这个指针有数据访问，在使用链表的时候我们给一个有类型的指针，在操作的时候编译器有规律可循了，接下来只要链表数据访问的函数了，因为数据域是一个指针，因为没有修改TraverseList函数，那么给函数指针传递的一个指向指针的指针，所以修改遍历数据域访问函数如下 int TraverseList(List*,int (*)(ElemType *));/* 遍历访问，反问某个节点元素用函数处理 */ list.htypedef void * ElemType; typedef struct node { ElemType data; struct node * next; }ChainNode; typedef struct { ChainNode *head; int size; ChainNode *tail; }List; List * CreateList(void); /* 创建链表 */ void DestoryList(List*); /* 销毁链表 */ void ClearList(List*); /* 清空链表 */ int ListAppend(List*,ElemType); /* 追加元素 */ int ListInsert(List*,int,ElemType); /* 加入元素 */ int ListDelete(List *,int); /* 删除第几个元素 */
int GetElem(List*,int,ElemType *); /* 取得第几个元素的值用第三个参数返回 */ ChainNode * GetAddr(List *, int); /* 取得编号为N的元素所在地址 */ int TraverseList(List*,int (*)(ElemType *)); /* 遍历访问，反问某个节点元素用函数处理 */ ChainNode * NewChainNode( ElemType); list.c #include "list.h" /*==================*/ /*==================*/ List *CreateList() { List * pt = 0; ElemType data; pt=(List*)malloc( sizeof(List) ); if( !pt ) return 0; pt->head = NewChainNode(data ); if( ! pt->head ) { free(pt); return 0; } pt->tail = pt->head; return pt; } /*==================*/ void DestoryList(List * plist) { ClearList(plist); free(plist->head); plist->head = 0; free(plist); plist = 0;
(题)数据结构复习题
Ch3链表（共18题，11道算法设计题） 一、选择题 1、设单链表中结点的结构为（data, link）。已知指针q所指结点是指针p所指结点的直接前驱，若在*q与*p之间插入结点*s，则应执行下列哪一个操作？ （1）s->link = p->link；p->link = s；（2）q->link = s；s->link = p； （3）p->link = s->link；s->link = p；（4）p->link = s；s->link = q； Key：（2） 2、设单链表中结点的结构为（data, link）。已知指针p所指结点不是尾结点，若在*p之后插入结点*s，则应执行下列哪一个操作？ （1）s->link = p；p->link = s；（2）s->link = p->link；p->link = s； （3）s->link = p->link；p = s；（4）p->link = s；s->link = p；Key：（2） 3、设单链表中结点的结构为（data, link）。若想摘除结点*p的直接后继，则应执行下列哪一个操作？ （1）p->link = p->link->link；（2）p = p->link；p->link = p->link->link； （3）p->link = p->link；（4）p = p->link->link； Key：（1） 4、设单循环链表中结点的结构为（data, link），且rear是指向非空的带表头结点的单循环链表的尾结点的指针。若想删除链表第一个结点，则应执行下列哪一个操作？ （1）s = rear；rear = rear->link；free（s）； （2）rear = rear->link；free（rear）； （3）rear = rear->link->link；free（rear）； （4）s = rear->link->link；rear->link->link = s->link；free（s）；
【实验指导书】实验7：指针 (1)
（2014~2015学年-第1学期） 1. 理解指针、地址和数组间的关系。 2. 掌握通过指针操作数组元素的方法； 3. 掌握数组名作为函数参数的编程方式。 4. 掌握通过指针操作字符串的方法。 5. 了解掌握使用断点调试程序的方法。 二、实验环境： 操作系统：Window 8 编译环境：CodeBlock 13.02 三、实验要求及内容（根据实验要求，将整个实验过程需要的数据和截屏记录于此，并整理成实验步骤。）： 1.设计一个程序计算输入的两个数的和与差，要求自定义一个函数sum_diff(float op1，float op2，float *psum，float *pdiff)，其中op1和op2是输入的两个数，*psum和*pdiff是计算得出的和与差。 解： （1）流程图如图1所示： 图1 程序7-1的流程图
图2 实验7-1实验源代码 （3）运行结果（测试用例） 实验7-1运行结果如图3所示 图3 实验7-1运行结果 2. 输入n 个正整数，使用选择法将它们从小到大排序后输出。要求：利用所学指针的内容实现。 提示：在指针这一章所学的冒泡排序算法基础上改写。 解： （1）流程图如图1所示： 图1 程序7-2的流程图
图2 实验7-2实验源代码（3）运行结果（测试用例）实验7-2运行结果如图3所示 图3 实验7-2运行结果
3. 输入10个整数存入数组a ，再输入一个整数x ，在数组a 中查找x ，若找到则输出相应的下标，否则显示“Not found ”。要求定义和调用函数seach(int list[]，int n ，int x)，在数组list 中查找元素x ，若找到则返回相应的下标，否则返回-1，参数n 代表数组list 中元素的数量。试编写相应程序。 解：(1)流程图如图1 7-3的流程图 （2）源代码 源代码如图2所示
指针与链表练习
指针与链表练习 1、围绕着山顶有10 个洞，一只兔子和一只狐狸各住一个洞，狐狸总想吃掉兔子。一天兔子对狐狸说，你想吃我有一个条件，第一次隔一个洞找我，第二次隔两个洞找我，以后依次类推，次数不限。若能找到我，你就可以饱餐一顿，在没找到我之前不能停止。狐狸一想只有10 个洞，寻找的次数又不限，哪有找不到的道理，就答应了条件。结果就是没找着。现请你编写一程序，假定狐狸找了1000 次，兔子躲在哪个洞里才安全。 2、输入一串大写字母，用这些字母建立一个指针链表，然后输出这个链表。链表中可能有一些重复的字母，将重复的多余字母从链表中删除，只留下第1个，输出链表。再将剩余链表中的字符按ASCII码升序重排，然后输出该链表。 例如：输入：DSDFRSSDFGDKAHHAUJDJG 输出：DSDFRSSDFGDKAHHAUJDJG DSFRGKAHUJ ADFGHJKRSU 3、约瑟夫的新问题 源程序文件名 jsf.pas 可执行文件名 jsf.exe 输入文件名 jsf.in 输出文件名 jsf.out 时间限制 1秒 问题描述 将1～Ｍ这Ｍ个自然数按由小到大的顺序沿顺时针方向围成一圈。以Ｓ为起点，先沿顺时针方向数到第N个数就出圈，然后再沿逆时针方向数到第Ｋ个数再出圈，再沿顺时针方向数到第N个数就出圈，然后再沿逆时针方向数到第Ｋ个数再出圈，……。这样按顺时针方向和逆时针方向不断出圈，直到全部数都出圈为止。 请打印先后出圈的数的序列。 输入格式 文件中共4行，每行为一个自然数，分别表示M，S，N，K。M不超过1000。 输出格式 仅1行，先后出圈的数的序列，每个数之间有1个空格。 样例输入（jsf.in） 8 1 3 2
复习题1
一、选择题 1-1 下列关于数据和逻辑结构的叙述中，哪一个是不正确的（）。 A ) 数据的逻辑结构是数据间关系的描述 B) 数据的逻辑结构抽象反映数据元素间的逻辑关系 C) 数据的逻辑结构具体反映数据在计算机中的存储方式 D) 数据的逻辑结构分为线性结构和非线性结构 C 1-2 以下关于数据的存储结构的叙述中哪一条是正确的（）。 A) 数据的存储结构是数据间关系的抽象描述 B) 数据的存储结构是逻辑结构在计算机存储器中的实现 C) 数据的存储结构分为线性结构和非线性结构 D) 数据的存储结构对数据运算的具体实现没有影响 B 二、简答题 1-1 数据结构的存储方式有哪几种？ 1-2 算法的时间复杂度仅与问题的规模相关吗? 1-1 数据结构的存储方式有哪几种？ 【解析】 常用的存储表示方法有四种: 1 、顺序存储方法：它是把逻辑上相邻的结点存储在物理位置相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现。由此得到的存储表示称为顺序存储结构，通常借助程序语言的数组描述。 2 、链接存储方法：它不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系是由附加的指针字段表示。由此得到的存储表示称为链式存储结构, 通常借助于程序语言的指针类型描述。 3 、索引存储方法：除建立存储结点信息外，还建立附加的索引表来标识结点的地址。组成索引表的索引项由结点的关键字和地址组成。若每个结点在索引表中都有一个索引项，则该索引表称之为稠密索引（Dense Index ）。若一组结点在索引表中只对应一个索引项，则该索引表称为稀疏索引。 4 、散列存储方法：就是根据结点的关键字直接计算出该结点的存储地址。 1-2 算法的时间复杂度仅与问题的规模相关吗? 【解析】 算法的时间复杂度不仅与问题的规模相关，还与输入实例中的初始状态有关。但在最坏的情况下，其时间复杂度就是只与求解问题的规模相关的。我们在讨论时间复杂度时，一般就是以最坏情况下的时间复杂度为准的。 三、应用题: 分析以下程序段的时间复杂度。 int i ，j ，k ； for （i=0 ；i 〈n ；i++ 〉// ① for （j=0 ；j 〈n ；j++ 〉// ② { c[i][j]=0 ；// ③ for （k=0 ；k 〈n ；k++ 〉// ④ c[i][j]=c[i][j]+a[i][k]+b[k][j] ；// ⑤ }
C语言实验六实验报告——指针
一、实验项目名称 指针 二、实验目的 1．掌握指针的基本概念和基本用法。包括：变量的地址和变量的值，指针变量的说明、指针变量的初始化、指针的内容与定义格式、指针的基本运算等； 2．掌握数组与指针的关系并能够利用指针解决数组的相关问题； 3．掌握字符串与指针的关系并能够利用指针处理字符串的问题； 4．掌握指针与函数的关系并能够利用指针处理函数问题； 5．了解指向指针的指针的概念及其使用方法； 6．能够使用指针进行程序设计。 三、实验内容 有关指针的程序设计 1．编程实现：任意输入的10个数，求其平均值。 要求： （1）10个数采用scanf语句读入。 （2）利用指针实现对这10个数的访问。 （3）要求平均值的精度为小数后面2位。 2．编程实现：将一个任意整数插入到一个已排序的整数数组中，插入后数组中的数仍然保持有序。 要求： （1）整数数组由初始化方式输入。任意整数由scanf函数输入； （2）实现过程采用指针处理； （3）输出原始数组数据以及插入数据后的数组数据并加以相应说明。 3．编写函数newcopy（char *new，char *old），它的功能是删除old所指向的字符串中的小写字母，并将所得到的新串存入new中。 要求： （1）在主函数中以初始化方式输入一个字符串； （2）调用newcopy（）函数； （3）在主函数中输出处理后的结果。 4．编程实现：输入三个整数，按由大到小的顺序输出。
要求： （1）通过scanf函数输入三个数据并存入三个变量中； （2）利用指针实现从大到小输出； （3）修改程序，将三个整型数据改为字符型数据，输入三个字符，按从大到小数顺序输出； （4）修改程序，将三个字符型数据改为字符串数据，输入三个字符串，按从小到大顺序输出； （5）体会指针对不同数据处理的特点。 四、实验步骤及结果 一、 #include <> void main() { int a[10],n,sum=0; float aver;/* 定义平均数为浮点型*/ int *p=a;/*初始化*/ printf("Please input 10 numbers:\n"); for (n=0;n<10;++n) scanf("%d",&a[n]);/*输入十个数*/ for (n=0;n<10;++n) sum=sum+*(p+n);/*使用指针访问数据*/ aver=(float)sum/n; printf("Average is %.2f",aver);/*精确到小数点后两位*/ } 二、 #include <> void arr(int *a,int n);/*定义排序函数*/ void insert(int *a,int num);/*插入并排序函数*/ int n=10;/*定义数据个数，可修改*/ void main()