第15周的作业struct node
{
int data;
struct *next;
};
1.倒序建立一个链表并输出。
#include "stdio.h"
#include "stdlib.h"
struct node
{
int data;
struct node *next;
};
void main()
{
struct node *pa,*t;
int i;
pa=NULL;
scanf("%d",&i);
while(i!=-1)
{
t=(struct node*)malloc(sizeof(struct node));
if (t==NULL)
{
printf("申请空间失败!\n");
return;
}
t->data=i;
t->next=pa;
pa=t;
scanf("%d",&i);
}
printf("建立的链表为：\n");
t=pa;
while(t)
{
printf("%4d",t->data);
t=t->next;
}
printf("\n");
}
2.正序建立一个链表并输出。
#include "stdio.h"
#include "stdlib.h"
struct node
{
int data;
struct node *next;
};
void main()
{
struct node *head,*t,*tail;
int i;
head=NULL;
tail=head;
scanf("%d",&i);
while(i!=-1)
{
t=(struct node*)malloc(sizeof(struct node));
if (t==NULL)
{
printf("申请空间失败!\n");
return;
}
t->data=i;
if (head==NULL)
{
head=t;
tail=t;
}
else
{
tail->next=t;
tail=t;
}
scanf("%d",&i);
}
if (head)
tail->next=NULL;
printf("建立的链表为：\n");
t=head;
while(t)
{
printf("%4d",t->data);
t=t->next;
}
printf("\n");
}
3.在一个已建立好的链表中查找一个数据是否存在。如果存在，输
出是第几个结点。
#include "stdio.h"
#include "stdlib.h"
struct node
{
int data;
struct node *next;
};
void main()
{
struct node *head,*t,*tail;
int i,wz,found=0;
head=NULL;
tail=head;
scanf("%d",&i);
while(i!=-1)
{
t=(struct node*)malloc(sizeof(struct node));
if (t==NULL)
{
printf("申请空间失败!\n");
return;
}
t->data=i;
if (head==NULL)
{
head=t;
tail=t;
}
else
{
tail->next=t;
tail=t;
}
scanf("%d",&i);
}
if (head)
tail->next=NULL;
/*输出建立好的链表*/
t=head;
while(t)
{
printf("%4d",t->data);
t=t->next;
}
printf("\n");
printf("输入要查找的数：");
scanf("%d",&i);
wz=0;
t=head;
while(t)
{
wz++;
if(t->data==i)
{
found=1;
break;
}
t=t->next;
}
if(found)
printf("位置是:%d.\n",wz);
else
printf("%d不存在.\n",i);
}
4.在链表中删除一个数X。
#include "stdio.h"
#include "stdlib.h"
struct node
{
int data;
struct node *next;
};
void main()
{
struct node *head,*t,*tail;
int i,wz,found=0;
/*以正序的方式建立一个单向链表,假设每个结点的值不重复*/ head=NULL;
tail=head;
scanf("%d",&i);
while(i!=-1)
{
t=(struct node*)malloc(sizeof(struct node));
if (t==NULL)
{
printf("申请空间失败!\n");
return;
}
t->data=i;
if (head==NULL)
{
head=t;
tail=t;
}
else
{
tail->next=t;
tail=t;
}
scanf("%d",&i);
}
if (head) /*若链表不空，则把最后一个指针置空*/ tail->next=NULL;
/*输出建立好的链表*/
printf("建立好的链表是：");
t=head;
while(t)
{
printf("%4d",t->data);
t=t->next;
}
printf("\n");
/*删除一个数X*/
printf("输入要删除的数：");
scanf("%d",&i);
struct node *p,*q;
if (head==NULL)
{
printf("链表为空!不能删除!\n");
return;
}
if (head->data==i)
{
p=head;
head=head->next;
free(p);
}
else
{
p=head;
q=p->next;
while(q)
{
if(q->data==i)
{
p->next=q->next;
free(q);
q=p->next;
if (q==NULL)
break;
}
p=q;
q=q->next;
}
}
/*输出删除X后的链表*/
printf("删除X后的链表：");
t=head;
while(t)
{
printf("%4d",t->data);
t=t->next;
}
printf("\n");
}
5.已知两个链表pa和pb已有序（升序），把两个链表合并成一个新
的链表并保持有序。
假设两个链表都不空：
#include "stdio.h"
#include "stdlib.h"
struct node
{
int data;
struct node *next;
};
struct node * creatlist()
{
struct node *head,*t,*tail;
int i;
head=NULL;
tail=head;
scanf("%d",&i);
while(i!=-1)
{
t=(struct node*)malloc(sizeof(struct node));
if (t==NULL)
{
printf("申请空间失败!\n");
return NULL;
}
t->data=i;
if (head==NULL)
{
head=t;
tail=t;
}
else
{
tail->next=t;
tail=t;
}
scanf("%d",&i);
}
if (head)
tail->next=NULL;
return head;
}
struct node * mergelist(struct node *ha, struct node *hb) {
struct node *hc,*pa,*pb,*t;
hc=NULL;
pa=ha;
pb=hb;
while (pa && pb)
if(hc==NULL)
if (pa->data
{
hc=pa;
t=pa;
pa=pa->next;
}
else
{
hc=pb;
t=pb;
pb=pb->next;
}
else
if (pa->data
{
t->next=pa;
t=t->next;
pa=pa->next;
}
else
{
t->next=pb;
t=t->next;
pb=pb->next;
}
if (pa)
t->next=pa;
else
t->next=pb;
return hc;
}
void printlist(struct node *head) {
struct node *t;
t=head;
while(t)
{
printf("%4d",t->data);
t=t->next;
}
}
void main()
{
struct node *pa,*pb,*pc;
printf("以正序的方式输入第一个链表的内容：");
pa=creatlist();
printf("以正序的方式输入第二个链表的内容：");
pb=creatlist();
printf("建立好的第一个链表是：");
printlist(pa);
printf("\n");
printf("建立好的第二个链表是：");
printlist(pb);
printf("\n");
pc=mergelist(pa,pb);
printf("合并后的链表是：");
printlist(pc);
printf("\n");
}
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时为空链表）
链表专题复习 数组作为存放同类数据的集合，给我们在程序设计时带来很多的方便，增加了灵活性。但数组也同样存在一些弊病。如数组的大小在定义时要事先规定，不能在程序中进行调整，这样一来，在程序设计中针对不同问题有时需要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语言版用链表实现通讯录 “标头.h” #include
#include
链表的c语言实现（一） 准备：动态内存分配 一、为什么用动态内存分配 但我们未学习链表的时候，如果要存储数量比较多的同类型或同结构的数据的时候，总是使用一个数组。比如说我们要存储一个班级学生的某科分数，总是定义一个float型（存在0.5分）数组： float score[30]; 但是，在使用数组的时候，总有一个问题困扰着我们：数组应该有多大？ 在很多的情况下，你并不能确定要使用多大的数组，比如上例，你可能并不知道该班级的学生的人数，那么你就要把数组定义得足够大。这样，你的程序在运行时就申请了固定大小的你认为足够大的内存空间。即使你知道该班级的学生数，但是如果因为某种特殊原因人数有增加或者减少，你又必须重新去修改程序，扩大数组的存储范围。这种分配固定大小的内存分配方法称之为静态内存分配。但是这种内存分配的方法存在比较严重的缺陷，特别是处理某些问题时：在大多数情况下会浪费大量的内存空间，在少数情况下，当你定义的数组不够大时，可能引起下标越界错误，甚至导致严重后果。 那么有没有其它的方法来解决这样的外呢体呢？有，那就是动态内存分配。 所谓动态内存分配就是指在程序执行的过程中动态地分配或者回收存储空间的分配内存的方法。动态内存分配不象数组等静态内存分配方法那样需要预先分配存储空间，而是由系统根据程序的需要即时分配，且分配的大小就是程序要求的大小。从以上动、静态内存分配比较可以知道动态内存分配相对于景泰内存分配的特点： 1、不需要预先分配存储空间； 2、分配的空间可以根据程序的需要扩大或缩小。 二、如何实现动态内存分配及其管理 要实现根据程序的需要动态分配存储空间，就必须用到以下几个函数 1、malloc函数 malloc函数的原型为： void *malloc (unsigned int size) 其作用是在内存的动态存储区中分配一个长度为size的连续空间。其参数是一个无符号整形数，返回值是一个指向所分配的连续存储域的起始地址的指针。还有一点必须注意的是，当函数未能成功分配存储空间（如内存不足）就会返回一个N ULL指针。所以在调用该函数时应该检测返回值是否为NULL并执行相应的操作。下例是一个动态分配的程序： #include #include main() { int count,*array; /*count是一个计数器，array是一个整型指针，也可以理解为指向一个整型数组的首地址*/ if((array(int *) malloc(10*sizeof(int)))==NULL) { printf("不能成功分配存储空间。"); exit(1); } for (count=0;count〈10;count++) /*给数组赋值*/
《数据结构与算法》复习题 选择题 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语言链表的操作实例 有这样一个结构体char team//队伍名 int jifen//积分 int win//胜利场数 int lost//失利场数 现在有N个队伍,想把一个队伍信息存入一个链表结点，可增加删除队伍，修改队伍信息，用链表具体怎么实现。本人一直对链表不太清楚，想通过此例理解链表，谢谢各位高手赐教，最好注释详细，谢谢！ 最佳答案 一般连表程序在c语言中要用link list来实现，我贴一个我写的程序在这里，可以运行，这个程序里包含一个structer纪录学生信息，学生号码已极学生姓名，纪录通过insert_node 添加，通过delete_node删除，并在最开始的时候通过create list function来创建最原始的数据，不用理会里面的reverse function。 #include C语言链表的操作实例
相关主题
文本预览