线性表的链式表示和实现
线性表的顺序存储可以随机存取表中任一元素,缺点是在做插入或删除操作时,需要移动大量的元素。
线性表的链式存储不要求逻辑上相邻的元素在物理位置上也相邻,在做插入或删除操作时,不需要移动元素,但也失去了随机存取的特点。
1 线性链表
用一组任意的存储单元存储线性表的数据元素。整个链表的存取必须从头指针开始,头指针指向链表的第一个结点(即第一个数据元素的存储映像)的存储位置,最后一个元素没有直接后继,则线性链表中最后一个结点的指针为NULL。
上图为带头结点的非空单链表
/*带有头指针的单链表*/
#include <stdio.h>
#include <stdlib.h>
#define TRUE 1
#define FALSE 0
typedef int elemType;
typedef struct LNode{
elemType data;
struct LNode *next;
}LNode,*linkNode;
typedef struct{
linkNode head;
int length;
} linkList;
/*创建结点,分配内存*/
void makeNode(linkNode *p,elemType e){
*p = (linkNode)malloc(sizeof(LNode));
if(!(*p)){
printf("空间分配失败!");
exit(0);
}
(*p)->data = e;
return;
}
/*释放结点空间*/
void freeNode(linkNode *p){
free(*p);
*p = NULL;
}
/*取头结点*/
linkNode getHead(linkList *L){
return L->head;
}
/*取当前结点p的后继结点*/
linkNode getNext(linkNode p){
return p->next;
}
/*判断当前链表是否为空链表*/
int listEmpty(linkList *L){
return getHead(L)->next == NULL ? 1: 0;
}
/*根据序号,获得对应的结点元素*/
linkNode getElem(linkList *L,int i){
if(i<0||i>L->length+1){
printf("查找的结点不存在!");
exit(0);
}else{
int j = 1;
linkNode e = getHead(L);
while(j< i && e){
e = e->next;
j++;
}
return e;
}
}
/*初始化链表*/
void initList(linkList *L){
linkNode p = (linkNode)malloc(sizeof(LNode));
if(p){
p->next=NULL;
L->length = 0;
L->head = p;
printf("空间分配成功!\n");
}else{
printf("空间分配失败!\n");
}
}
/*清空链表*/
void clearList(linkList *L){
linkNode p = getHead(L);
linkNode q;
while(p->next == NULL){
q = p;
p = p->next;
freeNode(&q);
}
p->next = NULL;
L->length = 0;
return;
}
/*销毁链表*/
void destroyList(linkList *L){
clearList(L);
freeNode(&L->head);
return;
}
/*在指定位置插入元素*/
void listInsert(linkList *L,int i,elemType e){
linkNode p = getElem(L,i);
linkNode s;
makeNode(&s,e);
s->next = p->next;
p->next = s;
L->length++;
return;
}
/*删除指定位置的元素*/
void listDelete(linkList *L,int i,elemType e){
linkNode p = getElem(L,i);
linkNode q = p->next;
p->next = q->next;
e = q->data;
freeNode(&q);
L->length--;
return;
}
/*遍历链表*/
void listTraverse(linkList *L,void(*visit)(elemType)){
linkNode p = L->head->next;
int j;
while(p != NULL){
visit(p->data);
p = p->next;
}
printf("\n");
return;
}
void visit(elemType e){
printf("%d ",e);
}
int compare(elemType a,elemType b){
return a-b;
}
int main(){
linkList LA;
initList(&LA);
int i=1;
for(i;i<=5;i++){
listInsert(&LA,i,i*3);
}
listTraverse(&LA,visit);
elemType e;
listDelete(&LA,2,e);
listTraverse(&LA,visit);
clearList(&LA);
listTraverse(&LA,visit);
return 0;
}
分享到:
相关推荐
数据结构与算法笔记(三)线性表 定义线性表节点的结构.pdf
试分别以不同的存储结构实现线性表的就地逆置算法,即在原表的存储空间将线性表(a1,a2...,an)逆置为(an,an-1,...,a1)。 选题9:(难)单链表拆分。 将带头结点的单链表LA中分拆成LB和LC两条单链表,LA中的data域...
将一个整数线性表拆分成奇数和偶数线性表,课后习题,完整好用
利用C++实现了链表、栈、队列三种数据结构的类封装,并提供常用操作。通过自己实现线性表结构,可以对其原理有更深理解。
线性表双向链表链表详细代码,有三个小的程序,调试通过。
数据结构第三章课件,特殊线性表--栈、队列和串。
数据结构之线性表(三)——顺序存储结构(1定义与特点) 定义线性表节点的结构.pdf
《数据结构(C语言版)》 几个线性表的函数 都是自家打出来的代码
用数据结构把A和B两个线性表合并一下,再放入C表里,并排好顺序
实验三:线性表的应用.doc
这是数据结构上机要实现的课程其中包括线性表中的创建插入删除和连接 实现环境c++
山东大学 数据结构实验 线性表的操作 数据结构课程设计
供数据结构实验用,数据结构实验代码-线性表的加入与删除(类模板)
有两个指数递减的一元多项式,写一程序先求这两个多项式的和,再求它们的积。
本ppt简述数据结构线性表一章 一、线性表逻辑结构 (a1, a2, ……ai-1, ai, ai+1, …….an) n(n>=0)个元素的有限集。每个元素的类型是相同 ...三、线性表的操作 插入、删除、 定位、查找、排序 等
(提示:采用顺序表结构时,顺序表中每个表元素包含三类信息:学号,姓名,和年龄;采用单链表结构时,单链表中每个结点的数据域包含三类信息:学号,姓名,和年龄。) 再,根据键盘输入进行相关操作(查找,...
数据结构教学课件:第三讲 线性表.ppt
1.熟练掌握线性表的基本运算。 2.掌握顺序表和单链表结构上的插入和删除算法。 3.了解循环链表、双(循环)链表的结构特点和在其上施加的插入、删除等操作。 4. 掌握线性表的逻辑结构特点、顺序存储结构、链式存储...
(提示:采用顺序表结构时,顺序表中每个表元素包含三类信息:学号,姓名,和年龄;采用单链表结构时,单链表中每个结点的数据域包含三类信息:学号,姓名,和年龄。) 再,根据键盘输入进行相关操作(查找,...