数据结构 C语言算法线性表

数据结构

发布日期: 2022-09-11

文章字数: 3.9k

阅读时长: 16 分

数据结构之线性表

知识回顾

数据结构

逻辑结构
- 线性结构
  - 线性表
  - 栈（特殊线性表）
  - 队列（特殊线性表）
  - 字符串、数组、广义表
- 非线性结构
  - 树形结构
  - 图形结构
数据的存储结构
- 顺序存储
- 链式存储
数据的运算：检索、排序、插入…

线性表的定义和特点

线性表是具有相同特性的数据元素的一个有限序列

(a1,a2,…,ai-1,ai,ai+1,…an)

a1:线性起点
ai-1:ai的直接前趋
ai+1:ai的直接后继
an:线性终点
n=0时称为空表（n是表长）

同一线性表中的元素必定具有相同特性，数据元素之间的关系是线性关系

案例引入

案例一：一元多项式的运算：实现两个多项式的加、减、乘运算

案例一

案例二：稀疏多项式的运算

案例二

Q:那么数组C多大合适呢？

顺序存储结构存在的问题

存储空间分配不灵活

运算的空间复杂度高

—>选择链式存储结构
链式存储方法

案例三：图书信息管理系统

将图书表抽象为线性表
表中每本书抽象线性表中数据元素

两种方式

线性表中数据元素可以是简单类型，也可以是复杂类型

线性表的类型定义

抽象数据类型（ADT）

数据对象

数据对象关系集合

作用在数据对象上的基本操作

抽象数据类型线性表的定义如下：

ADT List{
   数据对象：D={ai|ai属于Elemset，(i=1,2,3...n，n>=0)}  

   数据关系：R={<ai-1，ai>|ai-1，ai属于D，(i=1,2,3...n)}

   基本操作：
   IntList(&L);
   DestoryList(&L);
   ListInsert(&L,i,e);
   ListDelete(&L,i,&e);
   ...
}ADT List

InitList(&L):构造一个空的线性表L
DestoryList(&L)：线性表已存在的条件下，销毁线性表
ClwanList(&L)：线性表已存在的条件下，清除线性表元素，置L为空表
ListEmpty(L)：线性表已存在的条件下，若L为空表，返回TRUE，否则返回FALSE
ListLength(L):线性表已存在的条件下，返回L中元素个数
GetElem(L,I,&e):线性表已存在的条件下，1<=i<=ListLength(L),用e返回线性表中第i个元素的值
LocateElem(L,e,compare()):线性表已存在的条件下，compare()是数据元素判定函数，返回L中第一个与e满足compare()的数据元素的位序。若这样的数据元素不存在则返回值为0
PriorElem(L,cur_e,&pre_e):线性表已存在的条件下，若cur_e是L的数据元素，且不是第一个，则用pre_e返回他的前趋，否则操作失败，pre_e无意义
NextElem(L,cur_e,&next_e):线性表已存在的条件下，若cur_e是L的数据元素，且不是最后一个，则用next_e返回他的后继，否则操作失败，next_e无意义
ListInsert(&L,i,e):线性表已存在的条件下，1<=i<=ListLength(L)+1，在L的第i个位置之前插入新的元素e，L的长度加1
ListDelete(&L,i,&e)：线性表已存在的条件下，1<=i<=ListLength(L)，删除L的第i个元素，并用e返回其值，L的长度-1
ListTraverse(&L,visited()):线性表已存在的条件下，依次对线性表中的每个元素调用遍历visited()

以上提及的运算是逻辑结构上定义的运算，只要给出这些运算功能是“做什么”，至于“如何做”，只有待确定了存储结构之后才考虑

线性表的顺序表示和实现

顺序存储：把逻辑上相邻的数据元素储存在物理上相邻的存储单元中的存储结构

线性表中的第一个数据元素a1的存储位置，称作线性表的起始位置或基地址

两种方式

假设线性表的每个元素需要占用k个存储单元，则第i+1个数据元素的存储位置和第i个数据元素的存储位置之间满足:LOC(ai+1)=LOC(ai)+k ；同时LOC(ai)=LOC(ai)+(i-1)*k

顺序表元素->数组元素
用一维数组表示顺序表

线性表长度可变但数组长度不可动态定义
->用以变量表示顺序表的长度属性

#define LIST INIT SIZE 100 //线性表存储空间的初始分配量  
typedef struct {
    ElemType elem[LIST_INIT_SIZE];
    int length; //当前长度
}SqList;

多项式的顺序结构储存结构类型定义

#define MAXSIZE 1000 //多项式可能达到的最大长度
typedef struct {  //多项式非零项的定义
  float p;  //系数
  int e;  //指数
}Polynomial;
   
typedef struct {  
  Polynomial *elem;  //储存空间的基地址
  int length;  //多项式中当前项的个数
}SqList;//多项式的顺序储存结构类型为SqList

图书表的顺序存储结构类型定义

#define MAXSIZE 1000 //图书表可能达到的最大长度
typedef struct {  //图书信息定义
  char no[20];
  char name[50];
  float price;
}Book;
   
typedef struct { 
  Book *elem;  //储存空间的基地址
  int length;  //图书表中当前图书个数
}SqList;//图书表的顺序储存结构类型为SqList

线性表的数据类型定义模板

类C语言有关操作

数组静态分配：

typedef struct { 
  ElemType data[MaxSize];  
  int length;  
}SqList;

data:首元素地址

数组动态分布

typedef struct { 
  ElemType *data;  
  int length;  
}SqList;

SqList L;
L.data=(Elem Type*)malloc(sizeof(Elem Type)*MaxSize);

malloc(m)函数：开辟m字节长度的地址空间，并返回这段空间的首地址
sizeof(x)运算：计算变量x的长度
free(p)函数：释放指针p所指变量的存储空间，即彻底删除一个变量

需要加载头文件<stdlib.h>

补充：

C++的动态存储分配

new 类型名T(初始列表)
功能：申请用于存放T类型对象的内存空间，并依初值列表赋值以初值
结果值：

成功：T类型指针，指向新分配内存
失败：0 （NULL）

int *p1 = new int;
或 int *p1 = new int（10）;
使用 delete 指针P 释放

线性表的顺序表示和实现

线性表类型的构造（回顾）：

typedef struct { 
  ElemType data[MaxSize];  
  int length;  
}SqList;

线性表变量L的定义以及成员读取：

SqList L;
L.elem;
//or
SqList *L;
L->elem;

补充：操作算法中用到的预定义常量和类型

算法1 线性表的初始化

Status InitList_Sq(SqList &L){
  L.elem=new ElemType[MAXSIZE];
  if(!L.elem) exit(OVERFLOW);
  L.length=0; //空表长度为0
  return OK;
}

算法2 线性表的销毁

void DestroyList(SqList &L){
 if(L.elem)delete L.elem;
}

算法3 线性表的清空

void CleanList(SqList &L){
 L.Length=0;
}

算法4 线性表的长度

int GetLength(SqList L){
 return(L.Length);
}

算法5 判断线性表是否为空

int IsEmpty(SqList L){
 if(L.Length==0)return 1;
 else return 0；
}

算法6 顺序表的取值（取值i元素）

int GetElem(SqList L, ElemType &e){
 if(i<1||i>L.length)return ERROR;

 e=L.elem[i-1];
 return OK;
}

算法7 顺序表的元素查找（顺序查找）

int LocateElem(SqList L, ElemType e){
 for(i=0；i<L.length;i++)
   if(L.elem[i]==e) return i+1;

 return 0;
}

算法8 顺序表的元素插入

Status ListInsert_Sq(SqList &L,int i,Elem Type e){
  if(i<1||i>L.length+1)return ERROR; //i值不合法
  if(L.length==MAXSIZE)return ERROR; //当前存储空间已满
  for(j=L.length-1;j>=i-1;j--)
   L.elem[j+1]=L.elem[j];
   L.elem[i-1]=e;
   L.length++; //表长+1
   return OK;
}

算法9 顺序表的元素删除

Status ListDelete_Sq(SqList &L,int i){
  if(i<1||i>L.length+1)return ERROR; //i值不合法
  for(j=i;j<=L.length-1;j++)
   L.elem[j-1]=L.elem[j];
   L.length--; //表长-1
   return OK;
}

线性表的链式表示和实现

链表结点的定义

typedef struct Lnode{
 ElemType data;  //结点的数据域
 struct Lnode *next;  //结点的指针域  
}Lnode,*LinkList;//LlinkList为指向结构体Lnode的指针类型

单链表L的定义：
定义链表L： LinkList L;
定义结点指针p： LNode *p; 、LinkList p;

例如，存储学生学号、姓名、成绩的单链表结点类型定义如下：

typedef struct student{
 char num[8];
 char name[8];
 int score;
 struct student *next;  
}Lnode,*LinkList;

不过为了统一链表的操作，通常这样定义：

typedef struct {
 char num[8];
 char name[8];
 int score; 
}ElemType;

typedef struct Lnode{
 ElemType data；
 struct Lnode *next;  
}Lnode,*LinkList;

算法1 单链表的初始化

Status InitList L(LinkList &L){
   L=new LNode;  //或 L=(LinkList)malloc (sizeof(LNode));
   L->next=NULL;
   return OK;
}

算法2 判断链表是否为空

空表：链表中无元素，称为空链表(头指针和头结点仍然在)

int ListEmpty (LinkList L){
 if(L->next) //非空
   return 0;
 else 
   return 1;
}

算法3 单链表的销毁

Status DestroyList_L(LinkList &L){
 Lnode *p;
 while(L){
   p=L;
   L=L->next;
   delete p;
 }
}

算法4 清空单链表

Status ClearList(LinkList &L){
   Lnode *p，*q；
   p=L->next;
   while(p){
     q=p->next;
     delete p;
     p=q;
   }
  L->next=NULL;
  return OK;
}

算法5 单链表表长

int ListLength_L(LinkList L){
   LinkList p; //Lnode *p;
    p=L->next; //p指向第一个结点
     i=0;
     while(p){
       i++;
       p=p->next;
     }
   return i;
}

算法6 取值

取单链表中第i个元素内容

Status GetElem L(LinkList L, int i,ElemType &e){
  p=L->next;
  j=1;
  while(p && j<i){
    p=p->next; ++j;
  }
  if(!p||j>i) return ERROR;  
  e=p->data;
  return OK;
}

算法7 按值查找

根据指定数据获取该数据所在的位置(地址)

Lnode *LocateElem_L(LinkList L,ElemType e){
  P=L->next;
  while(p&&p->data!=e)
     p=p->next;
  return p;
}

算法7-变化按值查找

根据指定数据获取该数据所在的位置序号

int LocateElem_L(LinkList L,ElemType e){
  P=L->next; j=1;
  while(p&&p->data!=e)
     {p=p->next;j++;}
  if(p)return j;
  else return 0;
}

算法8 插入-在第i个结点前插入值为e的新结点

Status ListInsert_L(LinkList &L,int i,ElemType e){
  P=L;j=0;
  while(p&&j<i-1)
     {p=p->next;++j;}
  if(p||j>i-1)return ERROR;
  s=new LNode; s->data=e;
  s->next=p->next;
  p->next=s;
  return OK;
}

算法9 删除-删除第i个结点

Status ListDelete_L(LinkList &L,int i,ElemType &e){
  P=L;j=0;
  while(p->next&&j<i-1){p=p->next;++j;}
     
  if(!p->next||j>i-1)return ERROR;
  q=p->next;
  p->next=q->next;
  e=q->data;
  delete q;
  return OK;
}

单链表各算法时间效率

查找：O(n)

插入和删除：一般情况下O(1),但如果从头查找，所消耗的时间复杂度为O(n)

算法10 单链表的建立

头插法：元素插入到链表头部

首先，在内存中找到一个空间存放头结点

L=new LNode;或L=(LinkList)malloc(sizeof(LNode));

将头结点置空

L->next=NULL;

依次插入其余结点，从最后一个结点开始

p=new LNode; p->data=an;

将L的next域赋值给p的next域，并将头结点L的next赋值为新结点P的地址

p=next=L->next; L->next=p;

继续放置前一个结点

p=new LNode; p->data=an-1

再接着做之前的步骤

p=next=L->next; L->next=p;
反复循环，直到所有元素都插入

//倒位序输入n个元素值
void CreateList_H(LinkList &L,int n){
   L=new LNode;
   L->next=NULL;
   for(i=n;i>0;--i){
     p=new LNode;
     scanf(&p->data);
     p->next=L->next;
     L->next=p;
   }
 }

尾插法：元素插入在链表尾部

//正位序输入n个元素值
void CreateList_H(LinkList &L,int n){
   L=new LNode;
   L->next=NULL;
   r=L;//尾指针r指向头结点
   for(i=0;i<n;++i){
     p=new LNode;
     scanf(&p->data);
     p->next=NULL;
     r->next=p;
     r=p;//r指向新的尾结点
   }
 }

循环链表

是一种头尾相接的链表

优点：从表中任意结点出发均可找到表中其他结点

循环列表没有NULL指针，故涉及遍历操作时，其终止条件就不再像非循环链表那样判断p或p->next 是否为空，而是判断他们是否等于头指针

循环条件:

单链表	单循环链表
p!=NULL	p!=L
P->next!=NULL	p->NEXT!=1

循环链表若经常需要对首尾进行操作，则设置尾指针更为合适

带尾指针循环链表的合并

p存表头结点，Tb表头连接到Ta表尾，释放Tb表头结点，修改指针

p=Ta->next;
Ta->next=Tb->next->next;
delete Tb->next;

算法描述

LinkList Connect(LinkList Ta,LinkList Tb){
   p=Ta->next;
   Ta->next=Tb->next->next;
   delete Tb->next;
   Tb->next=p;
   return Tb;
 }

双向链表

双向链表的结点结构

双向链表的结构定义

typedef struct DuLNode{
  Elemtype data;
  struct DuLNode *prior, *next;
}DuLNode,*DuLinkList;

双向循环链表

-让头结点的前驱指针指向链表的最后一个结点
-让最后一个结点的后继指向头结点

算法1 双向链表的插入

s->prior=p->prior;
p->prior->next=s;
s->next=p;
p->prior=s;

void LinkInsert_DuL(DuLinkList &L, int i,ElemType e){
   if(!(p=GetElemP_DuL(L,i)))return ERROR;
   s=new DuLNode;
   s->data=e;
   s->prior=p->prior;
   p->prior->next=s;
   s->next=p;
   p->prior=s;
   return OK;
}

算法2 双向链表的删除

p->prior->next=p->next;
p->next->prior=p->prior;

void LinkInsert_DuL(DuLinkList &L, int i,ElemType e){
   if(!(p=GetElemP_DuL(L,i)))return ERROR;
   e=p->data;
   p->prior->next=p->next;
   p->next->prior=p->prior;
   free(p);
   return OK;
}

单链表、循环链表和双向链表的时间效率比较

顺序表和链表的比较

链式存储结构的优点：

结点空间可以动态申请和释放
删除和插入时不需要移动数据元素

链式存储结构的缺点：

存储密度小，每个结点的指针域需额外占用存储空间

非随机存取结构，对任意结点的操作都要从头指针依指针链查找到该结点，增加了算法复杂度

案例1：一元多项式的运算

案例2：稀疏多项式的运算

结构建立：

typedef struct PNode{
    float coef;  //系数
    int expn;    //指数
    struct PNode *next; //指针域  
}PNode,*Polynomial;

多项式创建：

void CreatePolyn(Polynomial &P, int n){
   P=new PNode;
   P->next=NULL;
   for(i=1;i<=n;i++){
    s=new PNode;
    cin>>s->coef>>s->expn;
    pre=P;
    q=P->next;
    while(q&&q->expn<s->expn){
      pre=q; q=q->next;
    }
    s->next=q;
    pre->next=s;
   }
}

多项式相加：

案例3：图书信息管理系统

autumnwt

https://autumnwt.github.io/2022/09/11/shu-ju-jie-gou-zhi-xian-xing-biao/

本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 autumnwt !

数据结构 C语言算法线性表

数据结构之栈和队列

2022-10-04 数据结构

数据结构 C语言算法栈队列

PHP基础简记ch.1

2022-09-07 PHP

PHP 语言

数据结构之线性表

数据结构之线性表

知识回顾

线性表的定义和特点

案例引入

线性表的类型定义

线性表的顺序表示和实现

线性表的数据类型定义模板

类C语言有关操作

C++的动态存储分配

线性表的顺序表示和实现

算法1 线性表的初始化

算法2 线性表的销毁

算法3 线性表的清空

算法4 线性表的长度

算法5 判断线性表是否为空

算法6 顺序表的取值（取值i元素）

算法7 顺序表的元素查找（顺序查找）

算法8 顺序表的元素插入

算法9 顺序表的元素删除

线性表的链式表示和实现

相关术语

链表结点的定义

算法1 单链表的初始化

算法2 判断链表是否为空

算法3 单链表的销毁

算法4 清空单链表

算法5 单链表表长

算法6 取值

算法7 按值查找

算法7-变化 按值查找

算法8 插入-在第i个结点前插入值为e的新结点

算法9 删除-删除第i个结点

算法10 单链表的建立

循环链表

带尾指针循环链表的合并

双向链表

双向链表的结构定义

双向循环链表

算法1 双向链表的插入

算法2 双向链表的删除

单链表、循环链表和双向链表的时间效率比较

顺序表和链表的比较

案例1：一元多项式的运算

案例2：稀疏多项式的运算

案例3：图书信息管理系统

你的赏识是我前进的动力

算法7-变化按值查找