数据结构C语言实现——线性链表
declaration.h
#ifndef DECLARATION_H_INCLUDED
#define DECLARATION_H_INCLUDED
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
#define ElemType int
typedef ElemType* T
typedef int S
typedef struct LNode
        ElemT
        struct LNode *
}LNode, *LinkL
#endif // DECLARATION_H_INCLUDED
function.h
#ifndef FUNCTION_H_INCLUDED
#define FUNCTION_H_INCLUDED
void CreateList_L(LinkList *L, int n);
//逆序输入n个元素的值，简历带头结点的单链表L
Status ListInsert_L(LinkList *L , int i, ElemType e);
//在带头结点的单链线性表中第i个位置前插入元素e
Status ListDelete_L(LinkList *L, int i, ElemType e);
//在带头结点的单链线性表中，删除第i个元素并由e返回其值
Status GetElem_L(LinkList L, int i, ElemType *e);
//L为带头结点的单链表的头指针
//当第i个元素存在时将其值付给e并返回OK，否则返回ERROR
Status MergeList_L(LinkList *La, LinkList *Lb, LinkList *Lc);
//归并La和Lb表到Lc并按非递减序列排列
void PrintList_L(LinkList L);
//输出单链表中的内容
#endif // FUNCTION_H_INCLUDED
function.c
#include "declaration.h"
void CreateList_L(LinkList *L, int n)
*L=(LinkList)malloc (sizeof(LNode));
(*L)->next=NULL;
//先建立带头结点的单链表;->的优先级比*高不要漏掉这里的括号
for(i=n; i>0 ;i--)
p=(LinkList)malloc((sizeof(LNode)));//生成新节点
scanf("%d", &p->data);
p->next=(*L)->
//插入到表头
(* L)->next=p;
数据是倒着插入连表的，即最后输入的数在表头
}//CreateList_L
Status ListInsert_L(LinkList *L , int i, ElemType e)
LinkList p=*L,
ElemType j=0;
while( p && j
if(!p || j >i-1)
return ERROR;
//i小于1或大于表长加1
s=(LinkList)malloc(sizeof(LNode));
s->data=e;
s->next=p->
p->next=s;
//先连接后插入
return OK;
Status ListDelete_L(LinkList *L, int i, ElemType *e)
LinkList p=*L,
ElemType j=0;
while(p->next && j
if( !(p->next) || j > i-1)
return ERROR;//删除位置不合理
p->next=q->
return *e;
Status GetElem_L(LinkList L, int i, ElemType *e)
ElemType j=1;
while(p && j
if( !p || j>i)
return ERROR;
//第i个元素不存在
return *e;
}//GetElem_L()
Status MergeList_L(LinkList *La, LinkList *Lb, LinkList *Lc)
//La和Lb两个链表中数据非递减排列
//归并La和Lb表到Lc并按非递减序列排列
LinkList pa, pb,
int i=0,j=0;
pa=(*La)->
pb=(*Lb)->
printf("%x
%x",(int )pa,(int )pb);
(*Lc) =(LinkList)malloc(sizeof(LNode));
while( (int)pa && (int)pb)
if( (pa->data) data))
pc->next =
while( pa )
pc->next=//插入剩余段
while( pb)
pc=pb=NULL;
return OK;
}//MergeList_L()
void PrintList_L(LinkList L)
for(p=L->p;p=p->next)//L为链表的头结点数据域没有赋值
printf("%d
",p->data);
printf("\n");
#include "declaration.h"
#include "function.h"
int main()
LinkList *La, *Lb, *Lc;
La=(LinkList *)malloc(sizeof(LinkList));
Lb=(LinkList *)malloc(sizeof(LinkList));
Lc=(LinkList *)malloc(sizeof(LinkList));
printf("create la ,please enter 5 number:");
CreateList_L(La, 5);
printf("la=");
PrintList_L(*La);
printf("la表中第3个数是%d\n", GetElem_L(*La, 3, &e));
printf("删除la表中的第一个数是%d\n", ListDelete_L(La, 1,&e));
printf("after delete first member ,la=");
PrintList_L(*La);
printf("create lb ,please enter 4 number:");
CreateList_L(Lb, 4);
printf("lb=");
PrintList_L(*Lb);
ListInsert_L(Lb, 2, 3);
printf("after insert 3, lb =");
PrintList_L(*Lb);
printf("MergeList function ,Lc=\n");
if(MergeList_L(La, Lb, Lc) ==OK)
printf("merget success\n");
PrintList_L(*Lc);
printf("merget failed");
分别定义二级指针La,Lb,Lc，将它们作为参数传递到CreateList_L()函数中，这样我们就可以在局部的函数里面为
*La, *Lb, *Lc分配存储空间，这些空间在结束函数调用时是不会消失的。C语言中参数传递都是值传递的方式：若以变量的值作为形参，传入的是一份值的拷贝。函数无返回类型时，对变量值得改变仅在该调用函数内有效；若以指针或数组名坐形参，传递的是变量的地址，同样的在调用函数内对这个地址的改变不会扩散到这个函数外，但对这个地址所代表的内存空间进行赋值，这种改变是永久的，结束调用时也不会被释放。
在实现MergeList_L(LinkList *La, LinkList *Lb, LinkList *Lc)时，一开始忘记为*Lc分配地址空间，使pc成为野指针，结果运行时程序一直挂掉浪费了好长一段时间。切记指针使用时一定要初始化。
运行结果：用户名：lilin9105
文章数：105
评论数：119
访问量：174137
注册日期：
阅读量：1297
阅读量：3317
阅读量：453894
阅读量：1138527
51CTO推荐博文
一、线性表定义: & &线性表是一个线性结构，它是一个含有n≥0个结点的有限序列，其中的结点，有且仅有一个开始结点(第一元素)没有前驱但有一个后继结点，有且仅有一个终端结点（最后节点）没有后继但有一个前驱结点，其它的结点都有且仅有一个前驱和一个后继结点。一般地，一个线性表可以表示成一个线性序列：k1,k2,…,kn，其中k1是开始结点，kn是终端结点。
& &上述定义可以用下列图像记忆 & & 如一对有序序列(A,B,C,............Z)图表示为（^，A(第一节点，没有前驱但有一个后继结点),B,C ……(其它的结点都有且仅有一个前驱和一个后继结点)……….Z（最后节点,没有后继但有一个前驱结点），^） & &总结：凡是符合上图特点的均可以认为是线性表。二、线性表的顺序表示与链式表示的区别顺序表存储图如下 特点: & &一、逻辑上相邻的数据元素，物理存储位置也相邻。（逻物一致） & &二、顺序表的存储空间需要预先分配。 & & &优点：　　（1）方法简单，各种高级语言中都有数组，容易实现。（语言通用性）　　（2）不用为表示节点间的逻辑关系而增加额外的存储开销。(内存节约性)　　（3）顺序表具有按元素序号随机访问的特点。(逻物一致性) 缺点：　　（1）在顺序表中做插入、删除操作时，平均移动表中的一半元素，因此对n较大的顺序表效率低。（操作低效率）　　（2）需要预先分配足够大的存储空间，估计过大，可能会导致顺序表后部大量闲置；预先分配过小，又会造成溢出。（内存固定性） 链式表存储图如下特点：一、逻辑上相邻的数据元素，物理存储位置不一定相邻。（逻物不一定一致） 二、它使用指针实现元素之间的逻辑关系。并且，链表的存储空间是动态分配的。链表的最大特点是：插入、删除运算方便。（插入、删除方便） & &优点：(1)插入、删除运算方便。（插入、删除方便） & & (2)内存空间动态分配使得内存使用率高，内存不易溢出。(内存动态分配性) & &缺点：　（1）要占用额外的存储空间存储元素之间的关系，存储密度降低。存储密度是指一个节点中数据元素所占的存储单元和整个节点所占的存储单元之比。(内存浪费或内存有效使用率低)　　（2）链表不是一种随机存储结构，不能随机存取元素。（逻物不一致） & &总结： 顺序表是一种牺牲cpu为代价但节省内存的数据存储方式，链式表是以牺牲内存代价的高效率的存储方式。实践应用中怎样选取存储结构呢？ & &1).内存使用率一般以一顺序存储为主，但线性表的长度变化较大或者难以估计其存储规模时，宜采用动态链表作为存储结构。 & & 2)基于运算的考虑（时间） 如果不对线性表频发插入或删除操作，以顺序表优先考虑； & &否则以链式表优先考虑三、 & 线性列表代码： & &以顺序存储为例的代码如下：#include&stdio.h&
#include&malloc.h&
#include&stdlib.h&
#define ERROR 0
#define OK 1
#define OVERFLOW -2
#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10
typedef int S
typedef int ElemT
typedef struct
Status InitList_Sq(SqList &L)
L.elem = (ElemType *)malloc(LIST_INIT_SIZE * sizeof(ElemType));
if (!L.elem) exit(OVERFLOW);
L.length = 0;
L.listsize = LIST_INIT_SIZE;
return OK;
Status ListInsert_Sq(SqList &L, int i, ElemType e)
ElemType *newbase, *q, *p;
if(i & 1 || i & L.length + 1) return ERROR;
if(L.length &= L.listsize)
newbase = (ElemType *)realloc(L.elem, (L.listsize + LISTINCREMENT) * sizeof(ElemType));
if(!newbase) exit(OVERFLOW);
L.listsize += LISTINCREMENT;
q = &(L.elem[i - 1]);
for(p = &(L.elem[L.length - 1]); p &= --p)
*(p+1) = *p;
return OK;
Status CreateList_Sq(SqList &L, int n){
printf("Please input %d elements:\n", n);
for(i = 1; i &= i++){
scanf("%d",&e);
ListInsert_Sq(L, i, e);
return OK;
Status DeleteList_Sq(SqList &L,int i, ElemType *e){
ElemType *p, *q;
if(i &= 0 || i & L.length) return ERROR;
p = &L.elem[i-1];
q = L.elem + L.
for(++p; p & ++p)
*(p - 1) = *p;
return OK;
Status LocateElem(SqList L, int num){
int i = 1;
ElemType *p;
while (i &= L.length && *p != num )
if(i & L.length)
Status ListAscend_Sq(SqList &L){
for(i = 0; i & L. i++)
for(j = i+1; j & L. j++)
if(L.elem[j] & L.elem[k])
if(k != i)
t = L.elem[i];
L.elem[i] = L.elem[k];
L.elem[k] =
return OK;
void Print_Sq(SqList L)
for(i = 0; i & L. i++)
printf("%d ",L.elem[i]);
printf("\n");
void main()
Status i, e, num, de, location, position,
SqList MyL
InitList_Sq(MyList);//初始化
CreateList_Sq(MyList, 10);//创建
printf("\n");
printf("Please input the number's position and the number to be inserted:");
scanf("%d,%d", &i, &e);
ListInsert_Sq(MyList,i, e);
printf("\n");
printf("Inserted list:\n");
Print_Sq(MyList);
printf("\n");
printf("Please input the position(to be deleted):");
scanf("%d", &position);
result = DeleteList_Sq(MyList, position, &de);
if(result == OK)
printf("The %dth element %d has been deleted.\n", position, de);
Print_Sq(MyList);
printf("\n");
printf("Please input the located number:");
scanf("%d",&num);
location = LocateElem(MyList, num);
if(location & 1)
printf("DO NOT EXIST!");
printf("Location:%d",location);
printf("\n\n");
ListAscend_Sq(MyList);//排序
printf("\n\n");
printf("The sorted list by ascending:\n");
Print_Sq(MyList);//输出
printf("\n");
free(MyList.elem);//释放空间
} & &以链式存储为例的代码如下：#include&stdio.h&
#include&stdlib.h&
#define TRUE
#define FALSE
#define OK
#define ERROR
#define INFEASIBLE
typedef int S
typedef int ElemT
typedef struct LNode {//定义类型链式节点
struct LNode *
}LNode, *LinkL
Status InitList_L(LinkList &L){//初始化链表L，链表的节点个数初始化data = 0； next = null
L = (LinkList)malloc(sizeof(LNode));//分配内存空间
if(!L) return ERROR;
L-&data = 0;//节点个数,或称为表长（表的长度）
L-&next = NULL;
return OK;
Status Insert_L(LinkList &L, int i, ElemType e){//向链表插入元素e
LNode *p, *q;
int j = 0;
while(p && j & i - 1){
p = p-& ++j;
if(!p || j & i - 1) return ERROR;
q = (LinkList)malloc(sizeof(LNode));
q-&data =//insert element
q-&next = p-&
L-&data++;//每插入也节点，表长自加1
return OK;
Status Delete_L(LinkList &L,int i, ElemType e){//删除节点e
LNode *p, *q;
int j = 0;
while(p-&next && j & i - 1){
if(!(p-&next) || j & i - 1) return ERROR;
p-&next = q-&
L-&data--;//每删除一个节点，表长自减1
return OK;
Status GetElem_L(LinkList L, int i, ElemType &e){//获取第i个元素，赋值于e
int j = 1;
while(p && j & i){
if(!p || j & i)
return ERROR;
return OK;
Status Create_L(LinkList &L){//创建链表，赋值元素
printf("Please input data&9999&ending\n");
scanf("%d", &temp);
while(temp != 9999){
Insert_L(L, L-&data+1, temp);
scanf("%d", &temp);
return OK;
Status Traverse_L(LinkList L){//遍历线性表
LNode *p = L-&
printf("List contains %d elements:\n",L-&data);
printf("%5d--&",p-&data);
printf("NULL\n");
return OK;
Status DeleteBet(LinkList &L, ElemType mink, ElemType maxk){//删除值在(mink,maxk)之间的值
LinkList p,
if((mink &= maxk) ||(p-&next == NULL)) exit(ERROR);
if(p-&next-&data & mink){
while(p-&next-&data & maxk){
p-&next = p-&next-&
L-&data --;
return OK;
LinkList L; int i, i1, i2, e, e1, e2, j1, j2;
InitList_L(L);//初始化链表
Create_L(L);//赋值链表
printf("The length is:%d\n", L-&data);
Traverse_L(L);//遍历输出节点值
printf("GetElem i:");
scanf("%d", &i);
GetElem_L(L, i, e);
printf("The NO.%d element is:%d \n", i, e);
printf("InsertPosition:");
scanf("%d", &i1);
printf("Insert element:");
scanf("%d", &e1);
Insert_L(L, i1, e1);
Traverse_L(L);//遍历输出节点值
printf("Delete position:"); scanf("%d", &i2);
Delete_L(L, i2, e2);
Traverse_L(L);//遍历输出节点值
printf("\nDelete between(a,b):");
scanf("%d,%d",&j1, &j2);
DeleteBet(L, j1, j2);
printf("The result is:%d\n");
Traverse_L(L);//遍历输出节点值
}四、知识点回顾线性表的链式存储及特点C逻物不一定一致、顺序存取、空间利用充分、插删方便• 单链表(线性链表)及C语言实现• 头指针、头结点、首元结点• 单链表的建立、查找、插入、删除、输出• 单链表与顺序表的比较，及挑本文出自 “” 博客，请务必保留此出处
了这篇文章
类别：┆阅读(0)┆评论(0)数据结构教案-辽宁工程技术大学.ppt -max上传文档投稿赚钱-文档C2C交易模式-100%分成比例文档分享网
数据结构教案-辽宁工程技术大学.ppt
文档名称：数据结构教案-辽宁工程技术大学.ppt
格式：ppt&&&大小：9.47MB&&&总页数：543
可免费阅读页数：543页
下载源文档需要：16元人民币
预览与实际下载的一致，文档内容不会超过预览的范围，下载前请务必先预览，自行甄别内容是否完整、是否存在文不对题等情况（本网站为文档分享平台性质），一旦付费下载，本站不支持退款
我已知晓：实际下载内容以预览为准！
文档介绍：数据结构第1章　绪　论1.1什么是数据结构1.2学习数据结构的意义1.3数据结构涵盖的主要内容1.4什么是抽象数据类型1.5算法效率的度量数据结构产生的背景例3多叉路口交通灯管理问题1.1什么是数据结构是相互之间存在一种或多种特定关系的数据元素的集合，表示为：数据data——所有能被计算机识别、存储和处理的符号的集合（包括数字、字符、声音、图像等信息）。数据元素dataelement——是数据的基本单位，具有完整确定的实际意义又称元素、结点，顶点、记录等）。数据项Dataitem——构成数据元素的项目。是具有独立含义的最小标识单位（又称字段、域、属性等）。1.2学习数据结构的意义　　计算机内的数值运算依靠方程式，而非数值运算（如表、树、图等）则要依靠数据结构。　　数据结构是一门学科，针对非数值计算的程序设计问题，研究计算机的操作对象以及它们之间的关系和操作等等。1.3数据结构涵盖的内容（1）SD,RDa,b,c,d,e,fRa,e,b,c,c,a,e,f,f,dd1d5d2d4d3　　　答：物理结构亦称存储结构，是数据的逻辑结构在计算机存储器内的表示（或映像）。它依赖于计算机。答：在数据的逻辑结构上定义的操作算法。它在数据的存储结构上实现。1.4什么是抽象数据类型数据类型与抽象数据类型的区别抽象数据类型如何定义例：给出自然数NaturalNumber的抽象数据类型定义。抽象数据类型如何表示和实现抽象数据类型可以通过固有的数据类型（如整型、实型、字符型等）来表示和实现。1.5算法效率的度量什么是算法？如何评判算法的好坏？时间复杂度和空间复杂度如何表示？计算举例什么是算法？如何评判一个算法的好坏？算法中实现基本操作的语句（基本语句）重复执行的次数，称为算法的频度。记作：TnOfn随问题规模n的增大，算法的频度Tn和fn的增长率同阶。例1：x+5;单个语句的频度为1，则程序段的时用户名：programnovice
访问量：1543
注册日期：
阅读量：1297
阅读量：3317
阅读量：453894
阅读量：1138527
51CTO推荐博文
&1.带头结点单链表的长度计算？
int&ListLength(LinkList&L)&{&&&&int&i&=&0;&&&&LinkList&p&=&L-&&&&&while(p){&&&&&&&++i;&&&&&&&p&=&p-&&&&&}&&&&return&i;&}&
i的初值设为0而非1，p指针设为头指针L的下一个节点，即链表除头指针之后的第一个结点，只有当p测试为非空
（while（p））之后才能增加结点数，因此此处是i = 0而不是i = 1，p是L-&next而不是L.
2. 获取带头结点单链表的第i个元素？
Status&GetElem(LinkList&L,int&i,ElemType&*e)&& &&&&&int&j=1;&&&&LinkList&p=L-&&&&&while(p&&j&i)&&&&{ &&&&&p=p-& &&&&&j++; &&&} &&&if(!p||j&i)&&&&&&return&ERROR; &&&*e=p-&&&&&return&OK; &}&
&&&& 为什么这里的j设计数器j = 1而不是前一个求单链表长度问题中的0呢(i = 0)?
&&&&&因为这里我们要求的是指向第i个元素的指针。注意到在求单链表长度的代码中，当跳出循环的时候p是为NULL的，也就是说p指向的实际上是第i个元素之后的下一个元素，所以当我们要求指向第i个元素的指针的时候，我们就必须让j的初值大1，这样当退出循环的时候就能保证指针p指向的是第i个元素了。(也可以用另外的一种方式，让初始的指针小1，即令p = L而不是L-&next，j的初值仍然设为0，也可以达到同样的目的，实际上这样做和前面的方法是一样的效果：保证在退出循环的时候p指向的是第i个元素而不是第i+1个元素。)
template&class&ElemType& &Node&ElemType&&*SimpleLinkList&ElemType&::GetElemPtr(int&position)&const&&{ &&&&&Node&ElemType&&*tmpPtr&=&&&&&&&&&&&&int&curPosition&=&0;&&&&&&&&&&&&&&&&&&&&&&while&(tmpPtr&!=&NULL&&&&curPosition&&&position) &&&&&&&&&&{ &&&&&&&&&tmpPtr&=&tmpPtr-& &&&&&&&&&curPosition++; &&&&&} &&&&&&if&(tmpPtr&!=&NULL&&&&curPosition&==&position) &&&&&{&&&&&&&&&&&&return&tmpP&& &&&&&} &&&&&else&&&&&{&&&&&&&&&&&&return&NULL;&&&& &&&&&} &&}&
&3.在带头结点的单链线性表L中第i个位置之前插入元素e ?
Status&ListInsert(LinkList&L,int&i,ElemType&e)&&{&&&&int&j=0;&&&LinkList&p=L,s;&&&while(p&&j&i-1)&&&&{&&&&&p=p-&&&&&&j++;&&&}&&&if(!p||j&i-1)&&&&&&return&ERROR;&&&s=(LinkList)malloc(sizeof(struct&LNode));&&&&s-&data=e;&&&&s-&next=p-&&&&p-&next=s;&&&return&OK;&}&
&& & &在这里能否用j = 1和 p = L-&next 代替上面代码中 j = 0 和 p = L 呢？
&& & &其实是不能的，因为插入的位置可以在第一个结点的地方，如果我们用j = 1 和 p = L-&next代替之后，就不能得到 i - 1位置是头结点的情形（因为一次都不循环while的情形下我们的p【待插入结点的前一个结点】已经是指向单链表中第一个结点 了），因此这里只好令j = 0， p = L，这样就能实现在头结点和第一个链表结点之间插入一个结点s了。本文出自 “” 博客，请务必保留此出处
了这篇文章
类别：┆阅读(0)┆评论(0)}