利用顺序栈将带头结点的单链表(a1,a2,…,an)逆置为(an,an-1,…,a1)

#include typedefintSElemType;

typedefstruct node

{int data;

struct node *next;

}linklist;

linklist *head;

#define STACK_INIT_SIZE 100

#define STACKINCREMENT 10 typedefstruct {

SElemType *base;

SElemType *top; intstacksize;

} SeqStack;

SeqStack *S;

linklist *creatlist()

{linklist *p,*q;

int n=0;

q=p=(struct node *)malloc(sizeof(linklist)); head=p;

p->next=NULL;

p=(struct node *)malloc(sizeof(linklist)); scanf("%d",&p->data);

while(p->data!=-1)

{

n=n+1;

q->next=p;

q=p;

p=(struct node *)malloc(sizeof(linklist)); scanf("%d",&p->data);

}

q->next=NULL;

return(head);

}

void print(linklist *head)

{linklist *p;

p=head->next;

if(p==NULL) printf("this is an empty list.\n");

else

{

do{printf("%6d",p->data); p=p->next;

}while(p!=NULL);

printf("\n");

}

}

intInitStack (SeqStack *S ){

S->base=(SElemType*) malloc (STACK_INIT_SIZE * sizeof(SElemType));

if (! S->base) return 0;

S->top =S->base;

S->stacksize =STACK_INIT_SIZE;

return 1;

}

int push(SeqStack *S,SElemType e)

{

if(S->top -S->base >= S->stacksize)

{

S->base = (SElemType *)realloc(S->base, (S->stacksize+STACKINCREMENT)*sizeof (SElemType));

if (! S->base ) return 0;

S->top=S->base+S->stacksize;

S->stacksize+= STACKINCREMENT; }

*S->top++=e;

return 1;

}

int Pop (SeqStack *S )

{

if(S->top ==S->base) return 0;

--S->top;

return *S->top ;

}

intstackempty(SeqStack *S)

{

if (S->top ==S->base ) return 1;

else return 0;

}

linklist *backlinklist(linklist *head)

{

linklist *p;

p=head->next;

InitStack (S );

while(p)

{

if( push(S,p->data));

p=p->next;

}

p=head->next;

while(!stackempty(S))

{

p->data=Pop(S);

p=p->next;

}

return(head);

}

void main()

{

linklist *head;

head=creatlist();

print(head);

head=backlinklist(head);

print(head);

}

《数据结构》实验报告 设计循环单链表

《数据结构》实验报告 1、实验名称:设计循环单链表 2、实验日期: 2013-3-26 3、基本要求： 1）循环单链表的操作，包括初始化、求数据元素个数、插入、删除、取数据元素； 2）设计一个测试主函数实际运行验证所设计循环单链表的正确性。 4、测试数据： 依次输入1，2，3，4，5，6，7，8，9，10，删除5，再依次输出数据元素。 5、算法思想或算法步骤: 主函数主要是在带头结点的循环单链表中删除第i个结点，其主要思想是在循环单链表中寻找到第i-1个结点并由指针p指示，然后让指针s指向a[i]结点，并把数据元素a[i]的值赋给x，最后把a[i]结点脱链，并动态释放a[i]结点的存储空间。 6、模块划分： 1）头文件LinList.h。头文件LinList.h中包括：结点结构体定义、初始化操作、求当前数据个数、插入一个结点操作、删除一个结点操作以及取一个数据元素操作； 2）实现文件dlb.cpp。包含主函数void main(void)，其功能是测试所设计的循环单链表的正确性。

7、数据结构： 链表中的结点的结构体定义如下： typedef struct Node { DataType data; struct Node *next; }SLNode; 8、源程序： 源程序存放在两个文件中，即头文件LinList.h和实现文件dlb.cpp。//头文件LinList.h typedef struct Node { DataType data; struct Node *next; }SLNode; void ListInitiate(SLNode **head) //初始化 { *head=(SLNode *)malloc(sizeof(SLNode)); //申请头结点，由head指示其地址 (*head)->next=*head; }

北京邮电大学 数据结构 实验一 带头结点的单链表构造

数据结构实验报告 实验名称：实验1——单链表的构造 学生姓名：XXXXNB 班级：XXXX 班内序号： 学号：XXXX 日期：XXXXX 1．实验要求 根据线性表的抽象数据类型的定义，完成带头结点的单链表的基本功能。 单链表的基本功能： 1、构造：使用头插法、尾插法两种方法 2、插入：要求建立的链表按照关键字从小到大有序 3、删除 4、查找 5、获取链表长度 6、销毁 7、其他：可自行定义 编写测试main()函数测试线性表的正确性。 2.程序分 编程完成单链表的一般性功能如单链表的构造：使用头插法、尾插法两种方法插入：要求建立的链表按照关键字从小到大有序，删除，查找，获取链表长度，销毁用《数据结构》中的相关思想结合C++语言基本知识编写一个单链表结构。本程序为使用方便，几乎不用特殊的命令，只需按提示输入即可，适合更多的用户使用。 2.1 存储结构 单链表的存储结构：

2.2 关键算法分析 1.头插法 自然语言描述：a.在堆中建立新结点 b.将a[i]写入到新结点的数据域 c.修改新结点的指针域 d.修改头结点的指针域,将新结点加入链表中 //在构建之初为了链表的美观性构造，进行了排序 代码描述： //头插法构造函数 template LinkList::LinkList(T a[], int n) { for (int i = n - 1; i >= 1; i--)//冒泡排序，对数组进行从小到大排序{ for (int j = 0; j < i; j++) { if (a[j]>a[j + 1]) { T t = a[j + 1]; a[j + 1] = a[j]; a[j] = t; } }

c语言 不带头结点的循环链表joseph问题

Joseph问题 题目描述: 原始的Joseph问题的描述如下：有n个人围坐在一个圆桌周围，把这n个人依次编号为1，…，n。从编号是start的人开始报数，数到第num个人出列，然后从出列的下一个人重新开始报数，数到第num个人又出列，…，如此反复直到所有的人全部出列为止。比如当n=6，start=1，num=5的时候，出列的顺序依次是5，4，6，2，3，1。 以下是不带头结点的循环链表算法 */ #include #include typedef int data_t; typedef struct node { data_t data; struct node *next; }listnode, *linklist; /*创建一个不带头节点的循环链表*/ listnode* CreatCycleList(int num) { int i = 2; listnode *head = NULL, *q = NULL, *p = NULL; head = (listnode*)malloc(sizeof(listnode)); head->data = 1; head->next = NULL; p = head; while(i <= num) { q = (listnode*)malloc(sizeof(listnode)); q->data = i; q->next = NULL; p->next = q; p = q; i++; } p->next = head;

return head; } listnode* Joseph(listnode *head, int start, int killNum) { int i; listnode *p, *q;//p遍历链表，q指向待宰的人 p = head; /* 找位置,p最后停在开始报数的前一个人处*/ if(start == 1) { while(p->next != head) { p = p->next; } } else { for(i = 1; i < start-1; i++) { p = p->next; } } /* 开杀*/ while(p != p->next) { for(i = 1; i < killNum; i++) { p = p->next; } q = p->next; p->next = q->next; printf("%d,",q->data); free(q); q = NULL; } return p; }

链表实验报告

C语言程序设计实验报告 实验一：链表的基本操作一·实验目的 1.掌握链表的建立方法 2.掌握链表中节点的查找与删除 3.掌握输出链表节点的方法 4.掌握链表节点排序的一种方法 5.掌握C语言创建菜单的方法 6.掌握结构化程序设计的方法 二·实验环境 1.硬件环境：当前所有电脑硬件环境均支持 2.软件环境：Visual C++6.0 三.函数功能 1. CreateList // 声明创建链表函数 2.TraverseList // 声明遍历链表函数 3. InsertList // 声明链表插入函数 4.DeleteTheList // 声明删除整个链表函数 5. FindList // 声明链表查询函数 四．程序流程图 五．程序代码 #include #include typedef int Elemtype; typedef int Status; typedef struct node//定义存储节点 { int data;//数据域 struct node *next;//结构体指针 } *linklist,node;//结构体变量，结构体名称 linklist creat (int n)//创建单链表 { linklist head,r,p;//定义头指针r,p,指针 int x,i; head=(node *)malloc(sizeof(node));//生成头结点

r=head;//r指向头结点 printf("输入数字:\n"); for(i=n;i>0;i--)//for 循环用于生成第一个节点并读入数据{ scanf("%d",&x); p=(node *)malloc(sizeof(node)); p->data=x;//读入第一个节点的数据 r->next=p;//把第一个节点连在头结点的后面 r=p;//循环以便于生成第二个节点 } r->next=0;//生成链表后的断开符 return head;//返回头指针 } void output (linklist head)//输出链表 { linklist p; p=head->next; do { printf("%3d",p->data); p=p->next; } while(p); printf("\n") } Status insert ( linklist &l,int i, Elemtype e)//插入操作 { int j=0; linklist p=l,s; while(jnext; ++j; } if(!p || j>i-1) return -1; else { s=(node *)malloc(sizeof(node)); s->data=e; s->next=p->next; p->next=s; return 1; } } Status delect ( linklist &l,int i, Elemtype &e)//删除操作 { int j=0; linklist p=l,q; while(jnext) { p=p->next; ++j; } if(!p->next || j>i-1) return -1;

单链表实验报告

计算机与信息技术学院综合性、设计性实验报告 一、实验目的 (1)熟悉顺序表的创建、取值、查找、插入、删除等算法，模块化程序设计方法。 二、实验仪器或设备 (1)硬件设备：CPU为Pentium 4 以上的计算机，内存2G以上 (2)配置软件：Microsoft Windows 7 与VC++6.0 三、总体设计(设计原理、设计方案及流程等) 设计原理： 单链表属于线性表，线性表的存储结构的特点是：用一组任意存储单元存储线性表的数据元素，这组存储单元可以是连续的，也可以是不连续的。因此，对于某个元素来说，不仅需要存储其本身的信息，还需要存储一个指示其直接后继的信息。 设计方案： 采用模块化设计的方法，设计各个程序段，最终通过主函数实现各个程序段的功能。设计时，需要考虑用户输入非法数值，所以要在程序中写入说可以处理非法数值的代码。 设计流程： 1. 引入所需的头文件； 2. 定义状态值； 3. 写入顺序表的各种操作的代码； 写入主函数，分别调用各个函数。在调用函数时，采用if结构进行判断输 入值是否非法，从而执行相应的程序 四、实验步骤(包括主要步骤、代码分析等) #include // EOF(=A Z 或F6),NULL #in clude // srand( ) ,rand( ),exit (n) #in clude // malloc( ),alloc( ),realloc() 等 #in clude // INT_MAX 等 #in clude #in clude #in clude // floor(),ceil( ),abs() #in clude // cout,ci n #in clude // clock( ),CLK_TCK,clock_t #defi ne TRUE 1 #defi ne FALSE 0 #defi ne OK 1 #defi ne ERROR 0 #defi ne INFEASIBLE -1

第三章 单链表 题目和答案

第2章自测卷答案 一、填空 1.顺序表中逻辑上相邻的元素的物理位置相互相邻。单链表中逻辑上相邻的元素的物理位置不 相邻。 2.在单链表中，除了首元结点外，任一结点的存储位置由其直接前驱结点值域指示。 3．在n个结点的单链表中要删除已知结点*p，需找到它的地址。 二、判断正误（在正确的说法后面打勾，反之打叉） 1. 链表的每个结点中都恰好包含一个指针。X 2. 链表的物理存储结构具有同链表一样的顺序。X 3. 链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动地将后续的各个单元向前移动。X 4. 线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。Y 5. 顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。Y 6. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。X 7. 线性表在物理存储空间中也一定是连续的。X 8. 线性表在顺序存储时，逻辑上相邻的元素未必在存储的物理位置次序上相邻。X 9. 顺序存储方式只能用于存储线性结构。X 10. 线性表的逻辑顺序与存储顺序总是一致的。X 三、单项选择题 （A）1. 链接存储的存储结构所占存储空间： （A）分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针 （B）只有一部分，存放结点值 （C）只有一部分，存储表示结点间关系的指针 （D）分两部分，一部分存放结点值，另一部分存放结点所占单元数 （B）2. 链表是一种采用存储结构存储的线性表； （A）顺序（B）链式（C）星式（D）网状 （D）3. 线性表若采用链式存储结构时，要求内存中可用存储单元的地址: （A）必须是连续的（B）部分地址必须是连续的 （C）一定是不连续的（D）连续或不连续都可以 （B）4．线性表Ｌ在情况下适用于使用链式结构实现。 （Ａ）需经常修改Ｌ中的结点值（Ｂ）需不断对Ｌ进行删除插入 （Ｃ）Ｌ中含有大量的结点（Ｄ）Ｌ中结点结构复杂 （C）5．单链表的存储密度 （Ａ）大于1；（Ｂ）等于1；（Ｃ）小于1；（Ｄ）不能确定 （A）6、在单链表的一个结点中有个指针。

栈的操作(实验报告)

实验三栈和队列 3.1实验目的： （1）熟悉栈的特点（先进后出）及栈的基本操作，如入栈、出栈等，掌握栈的基本操作在栈的顺序存储结构和链式存储结构上的实现； （2）熟悉队列的特点（先进先出）及队列的基本操作，如入队、出队等，掌握队列的基本操作在队列的顺序存储结构和链式存储结构上的实现。 3.2实验要求： （1）复习课本中有关栈和队列的知识； （2）用C语言完成算法和程序设计并上机调试通过； （3）撰写实验报告，给出算法思路或流程图和具体实现（源程序）、算法分析结果（包括时间复杂度、空间复杂度以及算法优化设想）、输入数据及程序运行结果（必要时给出多种可能的输入数据和运行结果）。 3.3基础实验 [实验1] 栈的顺序表示和实现 实验内容与要求: 编写一个程序实现顺序栈的各种基本运算，并在此基础上设计一个主程序，完成如下功能：（1）初始化顺序栈 （2）插入元素 （3）删除栈顶元素 （4）取栈顶元素 （5）遍历顺序栈 （6）置空顺序栈 分析: 栈的顺序存储结构简称为顺序栈,它是运算受限的顺序表。 对于顺序栈，入栈时，首先判断栈是否为满，栈满的条件为：p->top= =MAXNUM-1，栈满时，不能入栈; 否则出现空间溢出，引起错误，这种现象称为上溢。 出栈和读栈顶元素操作，先判栈是否为空，为空时不能操作，否则产生错误。通常栈空作为一种控制转移的条件。 注意： （1）顺序栈中元素用向量存放 （2）栈底位置是固定不变的，可设置在向量两端的任意一个端点 （3）栈顶位置是随着进栈和退栈操作而变化的，用一个整型量top（通常称top为栈顶指针）来指示当前栈顶位置 参考程序: #include #include #define MAXNUM 20

单链表的插入和删除实验报告

. 实验一、单链表的插入和删除 一、目的 了解和掌握线性表的逻辑结构和链式存储结构，掌握单链表的基本算法及相关的时间性能分析。 二、要求： 建立一个数据域定义为字符串的单链表，在链表中不允许有重复的字符串；根据输入的字符串，先找到相应的结点，后删除之。 三、程序源代码 #include"stdio.h" #include"string.h" #include"stdlib.h" #include"ctype.h" typedef struct node //定义结点 { char data[10]; //结点的数据域为字符串 struct node *next; //结点的指针域 }ListNode; typedef ListNode * LinkList; // 自定义LinkList单链表类型 LinkList CreatListR1(); //函数，用尾插入法建立带头结点的单链表

ListNode *LocateNode(); //函数，按值查找结点 void DeleteList(); //函数，删除指定值的结点void printlist(); //函数，打印链表中的所有值 void DeleteAll(); //函数，删除所有结点，释放内存 //==========主函数============== void main() { char ch[10],num[10]; LinkList head; head=CreatListR1(); //用尾插入法建立单链表，返回头指针printlist(head); //遍历链表输出其值 printf(" Delete node (y/n):");//输入“y”或“n”去选择是否删除结点scanf("%s",num); if(strcmp(num,"y")==0 || strcmp(num,"Y")==0){ printf("Please input Delete_data:"); scanf("%s",ch); //输入要删除的字符串 DeleteList(head,ch); printlist(head); } DeleteAll(head); //删除所有结点，释放内存 } //==========用尾插入法建立带头结点的单链表

数据结构___头插法和尾插法建立链表(各分有无头结点)

实验一链表的建立及基本操作方法实现 一、【实验目的】 、理解和掌握单链表的类型定义方法和结点生成方法。 、掌握利用头插法和尾插法建立单链表和显示单链表元素的算法。 、掌握单链表的查找（按序号）算法。 、掌握单链表的插入、删除算法。 二、【实验内容】 、利用头插法和尾插法建立一个无头结点单链表，并从屏幕显示单链表元素列表。 、利用头插法和尾插法建立一个有头结点单链表，并从屏幕显示单链表元素列表。 、将测试数据结果用截图的方式粘贴在程序代码后面。 重点和难点： 尾插法和头插法建立单链表的区别。 建立带头结点和无头结点单链表的区别。 带头结点和无头结点单链表元素显示方法的区别 三、【算法思想】 ) 利用头插法和尾插法建立一个无头结点单链表 链表无头结点，则在创建链表时，初始化链表指针。 当用头插法插入元素时，首先要判断头指针是否为空，若为空，则直接将新结点赋给,新结点指向空，即>，若表中已经有元素了，则将新结点的指向首结点，然后将新结点赋给即（>）。当用尾插法插入元素时，首先设置一个尾指针以便随时指向最后一个结点，初始化和头指针一样即。插入元素时，首先判断链表是否为空，若为空，则直接将新结点赋给即，若不为空，将最后一个元素的指向新结点即>，然后跳出这个语句，将新结点指向空，并且将指向新结点即>。 ) 利用头插法和尾插法建立一个有头结点单链表 链表有头结点，则在创建链表时，初始化链表指针> 。与无头结点区别在于，判断链表为空是根据>是否为空。 用头插法插入元素时，要判断链表是否为空，若为空则将新结点指向空，作为表尾，若不为空，则直接插入，将新结点指向头结点的指向，再将头结点指向新结点即>>>。 用尾插法插入元素时，首先也要设置一个尾指针以便随时指向最后一个结点，初始化，与无头结点区别就只是插入第一个元素时有区别。插入元素时，不需要判断链表是否为空，直接进行插入，代码>>。 ）带头结点和无头结点单链表元素显示方法的区别： 区别在于，显示时带头结点是从头结点开始即>，而无头结点链表是直接从开始即。 四、【源程序代码】 ) 利用头插法和尾插法建立一个无头结点单链表 <>

数据结构算法习题答案带头结点的循环链表表示队列,并且只设一个指针指向队尾元素结点(注意不设头指针)

数据结构算法题(假设以带头结点的循环链表表示队列,并且只设一个指针指向队尾元素结点(注意不设头指针)试编写相应的队列初始化,入队列和出队列的算法!) (提供两种答案哦！！！) 一： //既然是算法就不用源码了具体看注释 typedef int Datatype; typedef struct queuenode { Datatype data; struct queuenode *next; }QueueNode; //以上是结点类型的定义 typedef struct { queuenode rear; }LinkQueue; //只设一个指向队尾元素的指针 void InitQueue( LinkQueue &Q) { //置空队：就是使头结点成为队尾元素 =(queuenode*)malloc(sizeof(queuenode)) QueueNode* s; Q->rear = Q->rear->next;//将队尾指针指向头结点 while(Q->rear!=Q->rear->next) //当队列非空，将队中元素逐个出队 { s=Q->rear->next; Q->rear->next=s->next; free(s); } //回收结点空间 } int EmptyQueue( LinkQueue &Q) { //判队空 //当头结点的next指针指向自己时为空队 return Q->rear->next->next==Q->rear->next; }

void EnQueue( LinkQueue &Q, Datatype x) { //入队 //也就是在尾结点处插入元素 QueueNode *p=(QueueNode *) malloc (sizeof(QueueNode));//申请新结点 p->data=x; p->next=Q->rear->next;//初始化新结点并链入 Q-rear->next=p; Q->rear=p;//将尾指针移至新结点 } Datatype DeQueue( LinkQueue &Q,Datatype &x) { //出队,把头结点之后的元素摘下 Datatype t; QueueNode *p; if(EmptyQueue( Q )) Error("Queue underflow"); p=Q->rear->next->next; //p指向将要摘下的结点 x=p->data; //保存结点中数据 if (p==Q->rear) { //当队列中只有一个结点时，p结点出队后，要将队尾指针指向头结点 Q->rear = Q->rear->next; Q->rear->next=p->next; } else Q->rear->next->next=p->next;//摘下结点p free(p);//释放被删结点 return x; } 二： typedef struct Node { int data; struct Node *next; }Node,*CiLNode; typedef struct

第三章 链表 基本题

第三章链表 基本题 3.2.1单项选择题 1.不带头结点的单链表head为空的判定条件是 A.head=NULL B.head->next=NULL C.head->next=head D.head!=NULL 2.带头接待点的单链表head为空的判定条件是 A.head=NULL B.head->next=NULL C.head->next=head D.head!=NULL 3.非空的循环单链表head的尾结点(由p所指向)满足 A.p->head=NULL B.p=NULL C.p->next=head D.p=head 4.在循环双链表p的所指结点之后插入s所指结点的操作是 A.p->right=s; s->left=p; p->right->lefe=s; s->right=p->right; B.p->right=s; p->right->left=s; s->lefe=p; s->right=p->right; C.s->lefe=p; s->right=p->right; p->right=s; p->right->left=s; D.s->left=p; s->right=p->right; p->right->left=s; p->right=s; 5.在一个单链表中，已知q所指结点是所指结点p的前驱结点，若在q和p之间插入结点S，则执行 A.s->next=p->next; p->next=s; B.p->next=s->next; s->next=p; C.q->next=s; s->next=p; D.p->next=s; s->next=q; 6.在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行 A.s->next=p; p->next=s; B.s->next=p->next; p->next=s; C.s->next=p->next; p=s; D.p->next=s; s->next=p; 7.在一个单链表中，若删除p所指结点的后续结点，则执行 A.p->next=p->next->next; B.p=p->next; p->next=p->next->next; C.p->next=p->next D.p=p->next->next 8.假设双链表结点的类型如下： typedef struct linknode {int data; /*数据域*/ Struct linknode *llink; /*llink是指向前驱结点的指针域*/ Struct linknode *rlink; /*rlink是指向后续结点的指针域*/ }bnode 下面给出的算法段是要把一个所指新结点作为非空双向链表中的所指结点的前驱结点插入到该双链表中，能正确完成要求的算法段是 A.q->rling=p; q->llink=p->llink; p->llink=q;

C语言链表实验报告

链表实验报告 一、实验名称 链表操作的实现--学生信息库的构建 二、实验目的 （1）理解单链表的存储结构及基本操作的定义 （2）掌握单链表存储基本操作 （3）学会设计实验数据验证程序 【实验仪器及环境】计算机 Window XP操作系统 三、实验内容 1、建立一个学生成绩信息（学号，姓名，成绩）的单链表，按学号排序 2、对链表进行插入、删除、遍历、修改操作。 3、对链表进行读取（读文件）、存储（写文件） 四、实验要求 （1）给出终结报告（包括设计过程，程序）-打印版 （2）对程序进行答辩

五、实验过程、详细内容 1、概念及过程中需要调用的函数 （1）链表的概念结点定义 结构的递归定义 struct stud_node{ int num; char name[20]; int score; struct stud_node *next; }; （2）链表的建立 1、手动输入 struct stud_node*Create_Stu_Doc() { struct stud_node *head,*p; int num,score; char name[20]; int size=sizeof(struct stud_node); 【链表建立流程图】

2、从文件中直接获取 先建立一个 (3)链表的遍历 （4 ）插入结点 （5）删除结点 （6）动态储存分配函数malloc （） void *malloc(unsigned size) ①在内存的动态存储区中分配一连续空间，其长度为size ②若申请成功，则返回一个指向所分配内存空间的起始地址的指针 ③若申请不成功，则返回NULL （值为0） ④返回值类型：(void *) ·通用指针的一个重要用途 ·将malloc 的返回值转换到特定指针类型，赋给一个指针 【链表建立流程图】 ptr ptr ptr->num ptr->score ptr=ptr->next head pt r s s->next = ptr->next ptr->next = s 先连后断 ptr2=ptr1->next ptr1->next=ptr2->next free （ptr2）

带头结点单链表中数据就地逆置

实验3 ：带头结点单链表中数据就地逆置 一、实验目的： 1. 会定义单链表的结点类型； 2. 熟悉对单链表的一些基本操作和具体的函数定义； 3. 了解和掌握单链表的调用格式。 二、实验要求： 1. 认真阅读和掌握实验内容所给的程序，并上机运行； 2. 保存程序运行结果，并结合程序进行分析； 3. 尝试自己调试修改程序并试运行。 三、实验内容： 编写算法实现带头结点单链表的就地逆置，即利用原带头结点单链表的结点空间把数据元素序列逆置。 四、实验程序： #include #include #include typedef int datatype; typedef struct snode { datatype data; struct snode*next; }slnode; sllinitiate(slnode**head); linlistsort(slnode*head); int sllinsert(slnode*head,int i,datatype x); int slldelete(slnode*head,int i,datatype x); int sllget(slnode*head,int i,datatype*x); int sllnotempty(slnode*head); linlistsurt(slnode*head); linlistinsert(slnode*head,datatype x);

converse(slnode*head); main(void) { datatype test[6]={64,6,7,89,12,24}; slnode*head,*p; int n=6,i; sllinitiate(&head); for(i=1;i<=n;i++) sllinsert(head,i,test[i-1]); linlistsort(head); linlistinsert(head,25); converse(head); p=head->next; while(p!=NULL) { printf("%d",p->data); p=p->next; } } sllinitiate(slnode**head) { if((*head=(slnode*)malloc(sizeof(slnode)))==NULL)exit(1); (*head)->next=NULL; } int sllinsert(slnode*head,int i,datatype x) { slnode*p,*q; int j;

不带头结点的单链表head为空的条件

不带头结点的单链表head为空的判别条件是（）A．head!=NULL B．head—>link= =NULL C．head—>link= =head D．head= =NULL B 因为不带头结点,所以head的下一位是第一位 即判断head->link是否为空即可 不带头结点的单链表head为空的判定条件是什么head==NULL;头指针直接指向空 若有头结点，则为head->next==NULL head==null； 带头结点的是head->null; ( )不带头结点的单链表head为空的判定条件是 head==NULL head->next==NULL

head!=NULL head->next==head A head == NULL 带头结点的单链表head为空的判定条件（） 正确答案: B 你的答案: C (错误) head==NULL head->next==NULL head->next==head head!=NULL B 注意是带头结点，如果不带头结点就选A 为何头指针为head的带头结点的单链表判空条件head->next==null?其实一开始这里也是没啥问题的，只是突然产生了疑问点——head为头指针，储存了头结点的地址，按照我残余的一点指针知识，我总感觉不对，head只是个地址，咋可以直接head->next使用呢？其实哈，这里又产生了和我之前学结构体这个知识点一样的纠结点（嘿嘿，其实这里也算是结构体类型）——结构体 总之和结构体类型一样这个指向符号“->”,这里是有特殊规定的，

比如你定义个结构体类型 struct student { int age; float score; char name[100]; }*pstu，stu; 你用stu.age，pstu->age或者(*pstu).age都是一样可以取到成员变量的，这里的pstu它也是个地址，但是c语言就是这么规定了利用pstu->age可以取到其结构体内部成员变量（记住就好）所以不

链表基本操作实验报告

实验2 链表基本操作实验 一、实验目的 1．定义单链表的结点类型。 2．熟悉对单链表的一些基本操作和具体的函数定义。 3．通过单链表的定义掌握线性表的链式存储结构的特点。 二、实验内容与要求 该程序的功能是实现单链表的定义和主要操作。如：单链表建立、输出、插入、删除、查找等操作。该程序包括单链表结构类型以及对单链表操作的具体的函数定义和主函数。程序中的单链表（带头结点）结点为结构类型，结点值为整型。 要求： 同学们可参考指导书实验2程序、教材算法及其他资料编程实现单链表相关操作。必须包括单链表创建、输出、插入、删除操作，其他操作根据个人情况增减。 三、算法分析与设计。 1.创建单链表： 头结点L

...... 2.单链表插入

s s->data=x; s->next=p->next; p->next=s; 3.单链表的删除： p->next=p->next->next;

四、运行结果 1.单链表初始化 2.创建单链表 3.求链表长度 4.检查链表是否为空 5.遍历链表 6.从链表中查找元素 7.从链表中查找与给定元素值相同的元素在顺序表中的位置

8.向链表中插入元素 插入元素之后的链表 9.从链表中删除元素 删除位置为6的元素(是3) 10.清空单链表 五、实验体会 经过这次单链表基本操作实验，自己的编程能力有了进一步的提高，认识到自己以前在思考一个问题上思路不够开阔，不能灵活的表达出自己的想法，虽然在打完源代码之后出现了一些错误，但是经过认真查找、修改，最终将错误一一修正，主要是在写算法分析的时候出现了障碍，经过从网上查找资料，自己也对程

实验2-不带头结点的单链表

上海电力学院 数据结构实验报告 （2014/2015 学年第2学期）课程编号 250504704 课程名称数据结构 院（系） 专业 班级 学号 姓名 实验名称实验2 不带头结点的单链表 任课老师卢芳芳

实验2 不带头结点的单链表 1【实验目的与要求】 1、熟练掌握动态链表结构及有关算法的设计方法。 2、理解不带表头结点的单链表的特点，掌握其基本操作。 3、熟练掌握运用不带头结点链表表示特定形式的数据的方法，并设计出有关算法。 2【实验内容和步骤】 已知不带头结点的链表结构定义及头插法建表、尾插法建表和打印链表等函数定义如下（详见slnklist.h文件），基于该文件完成实验题1-实验4. #include #include /**************************************/ /* 链表实现的头文件，文件名slnklist.h */ /**************************************/ typedef int datatype; typedef struct link_node{ datatype info; struct link_node *next; }node; typedef node *linklist; /**********************************/ /*函数名称：creatbystack() */ /*函数功能：头插法建立单链表*/ /**********************************/ linklist creatbystack() { linklist head,s; datatype x; head=NULL; printf("请输入若干整数序列:\n"); scanf("%d",&x); while (x!=0) /*以0结束输入*/ { s=(linklist)malloc(sizeof(node)); /*生成待插入结点*/ s->info=x; s->next=head; /*将新结点插入到链表最前面*/ head=s; scanf("%d",&x); } return head; /*返回建立的单链表*/ } /**********************************/ /*函数名称：creatbyqueue() */ /*函数功能：尾插法建立单链表*/ /**********************************/ linklist creatbyqueue() { linklist head,r,s; datatype x; head=r=NULL; printf("请输入若干整数序列:\n"); scanf("%d",&x); while (x!=0) /*以0结束输入*/ { s=(linklist)malloc(sizeof(node));

链表基本操作实验报告记录

链表基本操作实验报告记录

————————————————————————————————作者：————————————————————————————————日期：

实验2链表基本操作实验 一、实验目的 1．定义单链表的结点类型。 2．熟悉对单链表的一些基本操作和具体的函数定义。 3．通过单链表的定义掌握线性表的链式存储结构的特点。 二、实验内容与要求 该程序的功能是实现单链表的定义和主要操作。如：单链表建立、输出、插入、删除、查找等操作。该程序包括单链表结构类型以及对单链表操作的具体的函数定义和主函数。程序中的单链表（带头结点）结点为结构类型，结点值为整型。 要求： 同学们可参考指导书实验2程序、教材算法及其他资料编程实现单链表相关操作。必须包括单链表创建、输出、插入、删除操作，其他操作根据个人情况增减。 三、算法分析与设计。 1.创建单链表： LinkedList LinkedListCreat( ) 创建链表函数 LinkedList L=LinkedListInit(),p, r; 调用初始化链表函数 r=L; r指向头结点 使用malloc函数动态分配存储空间，指针p指向新开辟的结点，并将元素存 放到新开辟结点的数据域， p=(LinkedList)malloc(sizeof(LNode)); p->data=x; r->next=p; 将新的结点链接到头结点r之后 r=p; r指向p结点 scanf("%d",&x); 满足条件循环输入链表元素 while(x!=flag) 当输入不为-1时循环 r->next=NULL; return L; 将链表结尾赋空值，返回头结点L 头结点L L ...... ^ ^ An A1 A2

带头结点的单链表(一)

带头结点的单链表（一）【基本操作训练】—— 现有以下定义，你的函数可以直接使用，无需再提交。 #define True 11 #define False 0 #define Ok 111 #define Error -111 #define List_Init_Size 10 #define ListIncrement 10 typedef int Status;//状态类型 typedef struct{ int num;//专家号，不重复，可用于查找专家 char name[30];//专家姓名，可能重复 }ElemType; //元素类型-----专家信息数据类型---------特别关注“数据元素”-------------// typedef ElemType ET; typedef struct Lnode{ ElemType data; struct Lnode *next; }LNode,*LinkList; 在招投标系统中，专家信息的更新换代比较频繁，假定采用“单链表”结构存储专家信息，请完成以下“带头结点的单链表”的部分基本操作： （1）（10分） 功能：构造一个带头结点的空单链表 L。 函数名：InitList_L 参数：单链表头指针L 返回值：成功返回Ok；否则，返回Error。 注意：考虑是否引用型参数、参数是怎样的数据类型、返回值类型应当如何? （2）（10分） 功能：求单链表L的长度 函数名：ListLength_L 参数：单链表头指针L 返回值：实际元素个数 注意：考虑是否引用型参数、参数是怎样的数据类型、返回值类型应当如何? （3）（20分） 功能：取表L中的第i个结点值赋值给参数e（注意i的取值范围） 函数名：GetElem_L 参数：单链表头指针L,位置i,数据元素e 返回值：取值成功返回Ok；否则，返回Error。 注意：考虑是否引用型参数、参数是怎样的数据类型、返回值类型应当如何? （4）（20分）Status ListInsert_L(LinkList L , int i , ET e);

数据结构-单链表实验报告

单链表实验报告 一、实验目的 1、帮助读者复习C++语言程序设计中的知识。 2、熟悉线性表的逻辑结构。 3、熟悉线性表的基本运算在两种存储结构上的实现，其中以熟悉链表的操作为侧重点。 二、实验内容 [问题描述] 实现带头结点的单链表的建立、求长度，取元素、修改元素、插入、删除等单链表的基本操作。 [基本要求] （1）依次从键盘读入数据，建立带头结点的单链表； （2）输出单链表中的数据元素 （3）求单链表的长度； （4）根据指定条件能够取元素和修改元素； （5）实现在指定位置插入和删除元素的功能。 三、算法设计 （1）建立带表头结点的单链表；首先输入结束标志，然后建立循环逐个输入数据，直到输入结束标志。 （2）输出单链表中所有结点的数据域值；首先获得表头结点地址，然后建立循环逐个输出数据，直到地址为空。 （3）输入x,y在第一个数据域值为x的结点之后插入结点y，若无结点x，则在表尾插入结点y;建立两个结构体指针，一个指向当前结点，另一个指向当前结点的上一结点，建立循环扫描链表。当当前结点指针域不为空且数据域等于x的时候，申请结点并给此结点数据域赋值为y，然后插入当前结点后面，退出函数；当当前结点指针域为空的时候，申请结点并给此结点数据域赋值为y，插入当前结点后面，退出函数。 （4）输入k，删除单链表中所有的结点k，并输出被删除结点的个数。建立三个结构体指针，一个指向当前结点，另一个指向当前结点的上一结点，最后一个备用；建立整形变量l=0；建立循环扫描链表。当当前结点指针域为空的时候，如果当前结点数据域等于k，删除此结点，l++，跳出循环，结束操作；如果当前结点数据域不等于k，跳出循环，结束操作。当当前结点指针域不为空的时候，如果当前结点数据域等于k，删除此结点，l++，继续循环操作；如果当前结点数据域不等于k，指针向后继续扫描。循环结束后函数返回变量l的值，l便是删除的结点的个数。