/* c2-2.h 线性表的单链表存储结构 */ struct LNode { ElemType data; struct LNode *next; }; typedef struct LNode *LinkList; /* 另一种定义LinkList的方法 */
/* bo2-2.c 单链表线性表(存储结构由c2-2.h定义)的基本操作(12个) */ Status InitList(LinkList *L) { /* 操作结果:构造一个空的线性表L */ *L=(LinkList)malloc(sizeof(struct LNode)); /* 产生头结点,并使L指向此头结点 */ if(!*L) /* 存储分配失败 */ exit(OVERFLOW); (*L)->next=NULL; /* 指针域为空 */ return OK; } Status DestroyList(LinkList *L) { /* 初始条件:线性表L已存在。操作结果:销毁线性表L */ LinkList q; while(*L) { q=(*L)->next; free(*L); *L=q; } return OK; } Status ClearList(LinkList L) /* 不改变L */ { /* 初始条件:线性表L已存在。操作结果:将L重置为空表 */ LinkList p,q; p=L->next; /* p指向第一个结点 */ while(p) /* 没到表尾 */ { q=p->next; free(p); p=q; } L->next=NULL; /* 头结点指针域为空 */ return OK; } Status ListEmpty(LinkList L) { /* 初始条件:线性表L已存在。操作结果:若L为空表,则返回TRUE,否则返回FALSE */ if(L->next) /* 非空 */ return FALSE; else return TRUE; } int ListLength(LinkList L) { /* 初始条件:线性表L已存在。操作结果:返回L中数据元素个数 */ int i=0; LinkList p=L->next; /* p指向第一个结点 */ while(p) /* 没到表尾 */ { i++; p=p->next; } return i; } Status GetElem(LinkList L,int i,ElemType *e) /* 算法2.8 */ { /* L为带头结点的单链表的头指针。当第i个元素存在时,其值赋给e并返回OK,否则返回ERROR */ int j=1; /* j为计数器 */ LinkList p=L->next; /* p指向第一个结点 */ while(p&&j<i) /* 顺指针向后查找,直到p指向第i个元素或p为空 */ { p=p->next; j++; } if(!p||j>i) /* 第i个元素不存在 */ return ERROR; *e=p->data; /* 取第i个元素 */ return OK; } int LocateElem(LinkList L,ElemType e,Status(*compare)(ElemType,ElemType)) { /* 初始条件: 线性表L已存在,compare()是数据元素判定函数(满足为1,否则为0) */ /* 操作结果: 返回L中第1个与e满足关系compare()的数据元素的位序。 */ /* 若这样的数据元素不存在,则返回值为0 */ int i=0; LinkList p=L->next; while(p) { i++; if(compare(p->data,e)) /* 找到这样的数据元素 */ return i; p=p->next; } return 0; } Status PriorElem(LinkList L,ElemType cur_e,ElemType *pre_e) { /* 初始条件: 线性表L已存在 */ /* 操作结果: 若cur_e是L的数据元素,且不是第一个,则用pre_e返回它的前驱, */ /* 返回OK;否则操作失败,pre_e无定义,返回INFEASIBLE */ LinkList q,p=L->next; /* p指向第一个结点 */ while(p->next) /* p所指结点有后继 */ { q=p->next; /* q为p的后继 */ if(q->data==cur_e) { *pre_e=p->data; return OK; } p=q; /* p向后移 */ } return INFEASIBLE; } Status NextElem(LinkList L,ElemType cur_e,ElemType *next_e) { /* 初始条件:线性表L已存在 */ /* 操作结果:若cur_e是L的数据元素,且不是最后一个,则用next_e返回它的后继, */ /* 返回OK;否则操作失败,next_e无定义,返回INFEASIBLE */ LinkList p=L->next; /* p指向第一个结点 */ while(p->next) /* p所指结点有后继 */ { if(p->data==cur_e) { *next_e=p->next->data; return OK; } p=p->next; } return INFEASIBLE; } Status ListInsert(LinkList L,int i,ElemType e) /* 算法2.9。不改变L */ { /* 在带头结点的单链线性表L中第i个位置之前插入元素e */ int j=0; LinkList p=L,s; while(p&&j<i-1) /* 寻找第i-1个结点 */ { p=p->next; j++; } if(!p||j>i-1) /* i小于1或者大于表长 */ return ERROR; s=(LinkList)malloc(sizeof(struct LNode)); /* 生成新结点 */ s->data=e; /* 插入L中 */ s->next=p->next; p->next=s; return OK; } Status ListDelete(LinkList L,int i,ElemType *e) /* 算法2.10。不改变L */ { /* 在带头结点的单链线性表L中,删除第i个元素,并由e返回其值 */ int j=0; LinkList p=L,q; while(p->next&&j<i-1) /* 寻找第i个结点,并令p指向其前趋 */ { p=p->next; j++; } if(!p->next||j>i-1) /* 删除位置不合理 */ return ERROR; q=p->next; /* 删除并释放结点 */ p->next=q->next; *e=q->data; free(q); return OK; } Status ListTraverse(LinkList L,void(*vi)(ElemType)) /* vi的形参类型为ElemType,与bo2-1.c中相应函数的形参类型ElemType&不同 */ { /* 初始条件:线性表L已存在 */ /* 操作结果:依次对L的每个数据元素调用函数vi()。一旦vi()失败,则操作失败 */ LinkList p=L->next; while(p) { vi(p->data); p=p->next; } printf("\n"); return OK; }
/* algo2-5.c 实现算法2.11、2.12的程序 */ #include"c1.h" typedef int ElemType; #include"c2-2.h" #include"bo2-2.c" void CreateList(LinkList *L,int n) /* 算法2.11 */ { /* 逆位序(插在表头)输入n个元素的值,建立带表头结构的单链线性表L */ int i; LinkList p; *L=(LinkList)malloc(sizeof(struct LNode)); (*L)->next=NULL; /* 先建立一个带头结点的单链表 */ printf("请输入%d个数据\n",n); for(i=n;i>0;--i) { p=(LinkList)malloc(sizeof(struct LNode)); /* 生成新结点 */ scanf("%d",&p->data); /* 输入元素值 */ p->next=(*L)->next; /* 插入到表头 */ (*L)->next=p; } } void CreateList2(LinkList *L,int n) { /* 正位序(插在表尾)输入n个元素的值,建立带表头结构的单链线性表 */ int i; LinkList p,q; *L=(LinkList)malloc(sizeof(struct LNode)); /* 生成头结点 */ (*L)->next=NULL; q=*L; printf("请输入%d个数据\n",n); for(i=1;i<=n;i++) { p=(LinkList)malloc(sizeof(struct LNode)); scanf("%d",&p->data); q->next=p; q=q->next; } p->next=NULL; } void MergeList(LinkList La,LinkList *Lb,LinkList *Lc)/* 算法2.12 */ { /* 已知单链线性表La和Lb的元素按值非递减排列。 */ /* 归并La和Lb得到新的单链线性表Lc,Lc的元素也按值非递减排列 */ LinkList pa=La->next,pb=(*Lb)->next,pc; *Lc=pc=La; /* 用La的头结点作为Lc的头结点 */ while(pa&&pb) if(pa->data<=pb->data) { pc->next=pa; pc=pa; pa=pa->next; } else { pc->next=pb; pc=pb; pb=pb->next; } pc->next=pa?pa:pb; /* 插入剩余段 */ free(*Lb); /* 释放Lb的头结点 */ Lb=NULL; } void visit(ElemType c) /* ListTraverse()调用的函数(类型要一致) */ { printf("%d ",c); } void main() { int n=5; LinkList La,Lb,Lc; printf("按非递减顺序, "); CreateList2(&La,n); /* 正位序输入n个元素的值 */ printf("La="); /* 输出链表La的内容 */ ListTraverse(La,visit); printf("按非递增顺序, "); CreateList(&Lb,n); /* 逆位序输入n个元素的值 */ printf("Lb="); /* 输出链表Lb的内容 */ ListTraverse(Lb,visit); MergeList(La,&Lb,&Lc); /* 按非递减顺序归并La和Lb,得到新表Lc */ printf("Lc="); /* 输出链表Lc的内容 */ ListTraverse(Lc,visit); }
相关推荐
数据结构C语言版-线性表的单链表存储结构表示和实现优质资料.doc
数据结构C语言版-线性表的单链表存储结构表示和实现.doc
建立一个单链表,实现单链表的初始化,插入、删除节点等功能,以及确定某一元素在单链表中的位置。 (1) 初始化单链表; (2) 依次采用尾插入法插入a,b,c,d,e元素; (3) 输出单链表L; (4) 输出单链表L的长度...
本文实例讲述了Python单链表原理与实现方法。分享给大家供大家参考,具体如下: Python实现单链表 关于链表 链表(Linked List)是由许多相同数据类型的数据项按照特定顺序排列而成的线性表。 链表中个数据项在...
(2)掌握线性表的链式表示和实现方法,特别是插入、删除操作。 (3)掌握运用C语言上机调试线性表的基本方法。 2.实验内容 (1)建立一个类型为整型链接表的头文件和基本操作,特别是初始化操作、插入操作、...
链表的具体存储表示为: ① 用一组任意的存储单元来存放线性表的结点(这组存储单元既可以是连续的,也可以是不连续的) ② 链表中结点的逻辑次序和物理次序不一定相同。为了能正确表示结点间的逻辑...
本PPT主要讲述线性表的类型定义 线性表的顺序表示和实现 线性表的链式表示和实现等
2、已知由单链表表示的线性表中,含有三类字符的数据元素(如:字母、数字和其它字符),设计算法构造三个以循环链表示的线性表,使每一个表中只含同一类的字符,且利用原表中的结点空间作为这三个表的空间。...
用它来表示线性表时,每一个数据元素占用一个结点(node)。一个结点一般由两个域组成,一个域存放数据元素data;另一个域存放一个指向链表中下一个结点的指针link,它指出下一个结点的开始存储地址。而最后一个结点的...
设双链表表示的线性表L=(a1,a2,....,an),试写一时间复杂度为O(n)的算法,将L改造为L=(a1,a2,,,,an....,a4,a2)。
2、已知由单链表表示的线性表中,含有三类字符的数据元素(如:字母、数字和其它字符),设计算法构造三个以循环链表示的线性表,使每一个表中只含同一类的字符,且利用原表中的结点空间作为这三个表的空间。...
第二章 - 线性表、单链表、静态单链表 第三章 - 链队列、循环队列、栈、栈链、离散时间模拟 第五章 - 广义表 第六章 - 二叉树链式存储、二叉树顺序存储、哈夫曼树与哈夫曼编码、树孩子表示法、树孩子兄弟表示法、树...
假设两个顺序线性表La和Lb分别表示两个集合A和B,如何实现A=A ∩B ? 实验2:单链表基本操作 一、 实验目的 1. 学会定义单链表的结点类型,实现对单链表的一些基本操作和具体的函数定义,了解并掌握单链表的类定义...
/* 线性表的单链表表示:类型和界面函数定义*/ /* 线性表的单链表表示:函数实现*/ /* 线性表的顺序表示:类型和界面定义*/ /* 线性表的顺序表示:函数实现*/ /* 用顺序表解决josephus问题的算法*/ /* 用循环单链表...
(3) 掌握单链表的遍历、插入和删除等操作算法,实现多项式相加。 二、 实验内容: 1、设有线性表 LA=(3,5,8,11)和 LB=(2,6,8,9,11,15,20); ① 若LA和LB分别表示两个集合A和B,求新集合 A=A U B('并'操作...
目的:通过实现线性表的算法设计,掌握数据结构研究方法,算法设计和分析方法。 要求:①掌握线性表的顺序存储结构和链式存储结构实现,体会两者特点,分析算法效率;②掌握在MyEclipse等集成开发环境中程序的运行和...
单链表是一种链式存取的数据结构,用一组地址任意的存储单元存放线性表中的数据元素。 单链表简介 链表中的数据是以结点来表示的,每个结点的构成:元素(数据元素的映象) + 指针(指示后继元素存储位置),元素就是...
掌握线性表的各种物理存储表示和C语言实现。 3.掌握单链表的各种主要操作的C语言实现。 4.通过实验理解线性表中的单链表存储表示与实现。 二、主要仪器及耗材 普通计算机 三、实验内容与要求 1、用C语言编写一个...
掌握线性表的链式存储结构——单链表的定义及其C语言实现。 掌握线性表在顺序存储结构即顺序表中的各种基本操作。 掌握线性表在链式存储结构——单链表中的各种基本操作。 6、认真阅读和掌握实验的程序。 7、上机...
单链表是一种链式存取的数据结构,用一组地址任意的存储单元存放线性表中的数据元素。链表中的数据是以结点来表示的,每个结点的构成:元素(数据元素的映象) + 指针(指示后继元素存储位置),元素就是存储数据的存储...