当前位置 博文首页 > Zhi Zhao的博客：数据结构之线性表
线性表是由
个同类型的数据元素构成的有限序列的线性结构。
（1）同一性：线性表由同类数据元素组成，每一个数据元素必须属于同一个数据对象；
（2）有穷性：线性表由有限个数据元素组成，表长度就是表中数据元素的个数；
（3）有序性：线性表中相邻数据元素之间存在着序偶关系。
线性表的顺序存储是指在内存中用一块地址连续的存储空间顺序存放线性表的各数据元素，使得线性表中在逻辑结构上相邻的数据元素存储在连续的物理存储单元中，即通过数据元素物理存储的连续性来反映数据元素之间逻辑上的相邻关系。
顺序表的结构体定义如下：
typedef int ElementType;
typedef struct
{
ElementType *array; // 存放元素的数组
int length; // 当前长度
int capacity; // 数组容量
}SqList;（1）顺序表的创建
// 构造一个空的顺序表
SqList *createList(int capacity)
{
SqList *L; // 定义顺序表
L=(SqList*)malloc(sizeof(SqList)); // 开辟一块内存空间给顺序表L
L->length=0; // 顺序表的长度为0
L->capacity=capacity; // 数组容量
L->array=(ElementType*)malloc(capacity*sizeof(ElementType)); // 在顺序表L上为数组开辟空间
return L;
}?（2）获得顺序表的数据元素
int GetElement(SqList *L,int i,ElementType *e)
{
if(i<1||i>L->length)
{
return 0;
}
*e=L->array[i-1];
return 1;
}?（3）顺序表的查找
顺序表的查找是指在顺序表中查找与给定值 e 相等的数据元素。下面采取从后向前查找的方式，若在顺序表 L 中找到与 e 相等的元素，则返回该元素在顺序表中的下标；否则，返回0。
int find(SqList *L,ElementType e)
{
int i;
i=L->length-1;
while(i>=0&&L->array[i]!=e){
i--;
}
if(i<0)
{
return 0;
}
return i;
}查找成功的平均比较次数为 (n+1)/2，时间复杂度为O(n) 。
（4）顺序表的插入
int insertlist(SqList *L,int i,ElementType e)
{
int k;
if(L->length>=L->capacity) // 1.判断顺序表的存储空间是否满
{
return 0;
}
if(i<1||i>L->length+1) // 2.判断插入位置i是否合法
{
return 0;
}
for(k=L->length-1;k>=i-1;k--)
{
L->array[k+1]=L->array[k]; // 3.从最后一个元素开始向后移动
}
L->array[i-1]=e; // 4.在第i个位置插入元素
L->length++; // 5.表长度加1
return 1;
}?在顺序表上做插入操作平均移动数据元素的次数为?n/2，时间复杂度为O(n) 。
（5）顺序表的删除
int deletelist(SqList *L,int i,ElementType *e)
{
int k;
if(i<1||i>L->length) // 1.判断删除位置i是否合法
{
return 0;
}
*e=L->array[i-1]; // 删除的第i个元素
for(k=i;k<L->length;k++)
{
L->array[k-1]=L->array[k]; // 2. 从i+1个元素开始向前移动
}
L->length--;
return 1;
}在顺序表上做删除操作平均移动数据元素的次数为 (n-1)/2，时间复杂度为O(n) 。
顺序表的合并，求两个顺序表中数据元素的并集
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define SIZE 100
typedef int ElementType;
typedef struct
{
ElementType *array; // 存放元素的数组
int length; // 当前长度
int capacity; // 数组容量
}SqList;
// 顺序表的创建
SqList *createList(int capacity)
{
SqList *L;
L=(SqList*)malloc(sizeof(SqList));
L->length=0;
L->capacity=capacity;
L->array=(ElementType*)malloc(capacity*sizeof(ElementType));
return L;
}
// 获得顺序表的元素
int GetElement(SqList *L,int i,ElementType *e)
{
if(i<1||i>L->length){
return 0;
}
*e=L->array[i-1];
return 1;
}
// 顺序表的查找
int find(SqList *L,ElementType e)
{
int i;
i=L->length-1;
while(i>=0&&L->array[i]!=e){
i--;
}
if(i<0)
{
return 0;
}
return i;
}
// 顺序表的插入
int insertlist(SqList *L,int i,ElementType e)
{
int k;
if(L->length>=L->capacity) // 1.判断顺序表的存储空间是否满
{
return 0;
}
if(i<1||i>L->length+1) // 2.判断插入位置i是否合法
{
return 0;
}
for(k=L->length-1;k>=i-1;k--)
{
L->array[k+1]=L->array[k]; // 3.从最后一个元素开始向后移动
}
L->array[i-1]=e; // 4.在第i个位置插入元素
L->length++; // 5.表长度加1
return 1;
}
// 顺序表的删除
int deletelist(SqList *L,int i,ElementType *e)
{
int k;
if(i<1||i>L->length) // 1.判断删除位置i是否合法
{
return 0;
}
*e=L->array[i-1]; // 删除的第i个元素
for(k=i;k<L->length;k++)
{
L->array[k-1]=L->array[k]; // 2. 从i+1个元素开始向前移动
}
L->length--;
return 1;
}
// 顺序表的长度
int listlength(SqList *L)
{
return L->length;
}
//按尾部插入法生成初始数据
void Addlist(SqList *L)
{
int value;
printf("请输入内容，-1结束\n");
scanf("%d",&value);
while(value!=-1)
{
insertlist(L,L->length+1,value); // 顺序表的插入
scanf("%d",&value);
}
}
//输出数据
void Outputlist(SqList *L)
{
int i;
for(i=0;i<L->length;i++)
{
printf("%d ",L->array[i]);
}
printf("\n");
}
// 顺序表的合并：取并集
void mergelist(SqList *L1,SqList *L2)
{
int L1_Len,L2_Len;
int i;
ElementType e;
L1_Len=listlength(L1); // 顺序表的长度
L2_Len=listlength(L2);
for(i=1;i<=L2_Len;i++)
{
GetElement(L2,i,&e); // 获得顺序表的元素
if(!find(L1,e)) // 在表L1中没找到该元素，则将该元素插入表L1中
{
insertlist(L1,L1->length+1,e); // 顺序表的插入
}
}
}
int main()
{
SqList *LA,*LB;
LA=createList(SIZE);
LB=createList(SIZE);
printf("尾部插入法生成初始数据：\n");
Addlist(LA);
printf("LA表中元素为：");
Outputlist(LA);
Addlist(LB);
printf("LB表中元素为：");
Outputlist(LB);
mergelist(LA,LB);
printf("LA和LB取并集后的元素为：");
Outputlist(LA);
return 0;
}线性表的链式存储是指在线性表中逻辑上相邻的数据元素在物理位置上并不一定相邻，它是通过‘链’建立起数据元素之间的逻辑关系。
C语言描述单链表类型如下：
typedef int ElementType;
typedef struct Node
{
ElementType data; // 数据域
struct Node *next; // 指针域
}node;
typedef struct Node *LinkList;（1）单链表的创建
/*===============================================================
CreateLinkList函数功能：
创建链表L, 并将给定数组a, 以及数组中元素个数n，尾部插入法建立链表
===================================================================*/
void createlist(LinkList *L,int n,int a[])
{
LinkList p,r;
int i;
(*L)=(LinkList)malloc(sizeof(node)); // 建立头结点
r=*L;
for(i=0;i<n;i++)
{
p=(LinkList)malloc(sizeof(node)); // 生成新结点
p->data=a[i];
r->next=p;
r=p;
}
r->next=NULL;
}（2）单链表的输出
/*===============================================================
Outputlist函数功能：
依次输出链表L中的每个数据
===================================================================*/
void Outputlist(LinkList L)
{
LinkList p;
p=L->next;
while(p!=NULL)
{
printf("%d ",p->data);
p=p->next;
}
printf("\n");
}时间复杂度为O(n) 。
（3）单链表的查找
单链表的查找有按值查找和按序号查找两种方式。
// 1.按值查找
LinkList findvalue(LinkList L,ElementType x)
{
LinkList p;
p=L->next;
while(p!=NULL && p->data!=x)
{
p=p->next;
}
return p;
}
// 2.按序号查找
LinkList locate(LinkList L,int i)
{
LinkList p;
int k=0;
p=L;
while(p!=NULL && k<i)
{
p=p->next;
k++;
}
return p;
}平均时间复杂度均为O(n) 。
（4）单链表结点的插入
// 单链表结点的插入：第i个位置插入数值x
int Insertlist(LinkList L,int i,ElementType x)
{
LinkList p,s;
p=locate(L,i-1); // 查找第i-1个结点，p指向该结点
if(p==NULL || i<1)
{
return 0;
}
s=(LinkList)malloc(sizeof(node));
s->data=x;
s->next=p->next;
p->next=s;
return 1;
}（5）单链表结点的删除
单链表结点的删除有按值删除和按序号删除两种方式。
// 1.按值删除
int Deletevalue(LinkList L,ElementType x)
{
LinkList p,q;
q=L;
p=L->next;
while(p!=NULL && p->data!=x)
{
q=p;
p=p->next;
}
if(p==NULL)
return 0;
else
{
q->next=p->next;
free(p);
return 1;
}
}
// 2.按序号删除
int Deletelocate(LinkList L,int i)
{
LinkList p,q;
ElementType x;
p=locate(L,i-1);
if(p==NULL || i<1 || p->next==NULL)
{
return 0;
}
q=p->next;
p->next=q->next;
x=q->data;
printf("删除的值为：");
printf("%d\n",x);
free(q);
return 1;
}?注意：一定要找到所删除结点的前驱结点。
删除算法的时间复杂度为O(n) 。
（6）以上单链表主要操作的全部程序
#include<stdio.h>
#include<stdlib.h>
typedef int ElementType;
typedef struct Node
{
ElementType data;
struct Node *next;
}node;
typedef struct Node *LinkList;
/*===============================================================
CreateLinkList函数功能：
创建链表L, 并将给定数组a, 以及数组中元素个数n，尾部插入法建立链表
===================================================================*/
void createlist(LinkList *L,int n,int a[])
{
LinkList p,r;
int i;
(*L)=(LinkList)malloc(sizeof(node)); // 建立头结点
r=*L;
for(i=0;i<n;i++)
{
p=(LinkList)malloc(sizeof(node)); // 生成新结点
p->data=a[i];
r->next=p;
r=p;
}
r->next=NULL;
}
/*===============================================================
Outputlist函数功能：
依次输出链表L中的每个数据
===================================================================*/
void Outputlist(LinkList L)
{
LinkList p;
p=L->next;
while(p!=NULL)
{
printf("%d ",p->data);
p=p->next;
}
printf("\n");
}
// 单链表的查找:1.按值查找；2.按序号查找
LinkList findvalue(LinkList L,ElementType x)
{
LinkList p;
p=L->next;
while(p!=NULL && p->data!=x)
{
p=p->next;
}
return p;
}
LinkList locate(LinkList L,int i)
{
LinkList p;
int k=0;
p=L;
while(p!=NULL && k<i)
{
p=p->next;
k++;
}
return p;
}
// 单链表结点的插入：第i个位置插入数值x
int Insertlist(LinkList L,int i,ElementType x)
{
LinkList p,s;
p=locate(L,i-1);
if(p==NULL || i<1)
{
return 0;
}
s=(LinkList)malloc(sizeof(node));
s->data=x;
s->next=p->next;
p->next=s;
return 1;
}
// 单链表的删除:1.按值删除；2.按序号删除
int Deletevalue(LinkList L,ElementType x)
{
LinkList p,q;
q=L;
p=L->next;
while(p!=NULL && p->data!=x)
{
q=p;
p=p->next;
}
if(p==NULL)
return 0;
else
{
q->next=p->next;
free(p);
return 1;
}
}
int Deletelocate(LinkList L,int i)
{
LinkList p,q;
ElementType x;
p=locate(L,i-1);
if(p==NULL || i<1 || p->next==NULL)
{
return 0;
}
q=p->next;
p->next=q->next;
x=q->data;
printf("删除的值为：");
printf("%d\n",x);
free(q);
return 1;
}
int main()
{
int A[]={0};
int i,j;
int N;
LinkList S;
ElementType e;
int select;
printf("请输入链表元素的个数：");
scanf("%d",&N);
for(i=0;i<N;i++)
{
scanf("%d",&A[i]);
}
createlist(&S,N,A);
printf("单链表中元素为：");
Outputlist(S);
while(1)
{
printf("\n\n");
printf(" 输入 1 在单链表中插入元素。\n");
printf(" 输入 2 则按位置删除单链表中的元素。\n");
printf(" 输入 3 则按值删除单链表中的元素。\n");
printf(" 输入 4 则显示单链表。\n");
printf(" 输入 5 则退出程序。\n");
printf("请选择输入操作：\n");
scanf("%d",&select);
switch(select)
{
case 1:{
printf("请输入要插入的位置：\n");
scanf("%d", &j);
printf("请输入要插入的数值：\n");
scanf("%d", &e);
Insertlist(S,j,e);
printf("插入后表中元素为：");
Outputlist(S);
}
break;
case 2:{
printf("请输入要删除的位置：\n");
scanf("%d", &j);
Deletelocate(S,j);
printf("删除后表中元素为：");
Outputlist(S);
}
break;
case 3:{
printf("请输入要删除的值：\n");
scanf("%d", &e);
Deletevalue(S,e);
printf("删除后表中元素为：\n");
Outputlist(S);
}
break;
case 4:{
printf("单链表中的元素为：\n");
Outputlist(S);
}
break;
case 5:printf("已退出程序！\n");exit(-1);break;
default:printf("输入错误，请重新输入！\n");break;
}
}
return 0;
}单链表的合并
例题1：有两个单链表LA和LB，它们的元素均为非递减有序序列。编写一个算法，将它们合并成一个单链表，要求合并后的单链表中的元素也是非递减有序序列，并且不需要额外申请结点空间。
#include<stdio.h>
#include<stdlib.h>
typedef int ElementType;
typedef struct Node
{
ElementType data;
struct Node *next;
}node;
typedef struct Node *LinkList;
/*===============================================================
CreateLinkList函数功能：
创建链表L, 并将给定数组a, 以及数组中元素个数n，尾部插入法建立链表
===================================================================*/
LinkList createlist(LinkList *L,int n,int a[])
{
LinkList p,r;
int i;
(*L)=(LinkList)malloc(sizeof(node)); // 建立头结点
r=*L;
for(i=0;i<n;i++)
{
p=(LinkList)malloc(sizeof(node)); // 生成新结点
p->data=a[i];
r->next=p;
r=p;
}
r->next=NULL;
return *L;
}
/*===============================================================
Outputlist函数功能：
依次输出链表L中的每个数据
===================================================================*/
void Outputlist(LinkList L)
{
LinkList p;
p=L->next;
while(p!=NULL)
{
printf("%d ",p->data);
p=p->next;
}
printf("\n");
}
// 单链表的查找:按值查找
LinkList findvalue(LinkList L,ElementType x)
{
LinkList p;
p=L->next;
while(p!=NULL && p->data!=x)
{
p=p->next;
}
return p;
}
// 单链表的合并：非递减有序序列
void mergelist1(LinkList LA,LinkList LB)
{
LinkList pa,pb,pr;
pa=LA->next;
pb=LB->next;
LA->next=NULL; // 此时LA为带头结点的空单链表
pr=LA; // pr为尾指针
while(pa!=NULL && pb!=NULL)
{
if(pa->data <= pb->data)
{
pr->next=pa;
pr=pa;
pa=pa->next;
}
else
{
pr->next=pb;
pr=pb;
pb=pb->next;
}
}
if(pa!=NULL)
pr->next=pa;
if(pb!=NULL)
pr->next=pb;
free(LB); // 释放空间
}
int main()
{
LinkList La,Lb;
int A[]={2,2,3};
int B[]={1,3,3,4};
int NA=sizeof(A) / sizeof(A[0]);
int NB=sizeof(B) / sizeof(B[0]);
createlist(&La,NA,A);
printf("序列A中的元素为：");
Outputlist(La);
createlist(&Lb,NB,B);
printf("序列B中的元素为：");
Outputlist(Lb);
mergelist1(La,Lb);
printf("序列A和序列B合并后的元素为：");
Outputlist(La);
}例题2：假设集合A用单链表LA表示，集合B用单链表LB表示，设计算法求这两个集合的差。
#include<stdio.h>
#include<stdlib.h>
typedef int ElementType;
typedef struct Node
{
ElementType data;
struct Node *next;
}node;
typedef struct Node *LinkList;
/*===============================================================
CreateLinkList函数功能：
创建链表L, 并将给定数组a, 以及数组中元素个数n，尾部插入法建立链表
===================================================================*/
LinkList createlist(LinkList *L,int n,int a[])
{
LinkList p,r;
int i;
(*L)=(LinkList)malloc(sizeof(node)); // 建立头结点
r=*L;
for(i=0;i<n;i++)
{
p=(LinkList)malloc(sizeof(node)); // 生成新结点
p->data=a[i];
r->next=p;
r=p;
}
r->next=NULL;
return *L;
}
/*===============================================================
Outputlist函数功能：
依次输出链表L中的每个数据
===================================================================*/
void Outputlist(LinkList L)
{
LinkList p;
p=L->next;
while(p!=NULL)
{
printf("%d ",p->data);
p=p->next;
}
printf("\n");
}
// 单链表的查找:按值查找
LinkList findvalue(LinkList L,ElementType x)
{
LinkList p;
p=L->next;
while(p!=NULL && p->data!=x)
{
p=p->next;
}
return p;
}
// 单链表的合并：两个集合的差，A-B，即得到所有属于集合A而不属于集合B的元素
void mergelist2(LinkList LA,LinkList LB)
{
LinkList pr,pa,temp;
pr=LA;
pa=LA->next;
while(pa!=NULL)
{
if(findvalue(LB,pa->data)!=NULL)
{
temp=pa; // temp为中间变量
pr->next=temp->next;
pa=temp->next;
free(temp);
}
else
{
pr=pa;
pa=pa->next;
}
}
}
int main()
{
LinkList La,Lb;
int A[]={2,2,3};
int B[]={1,3,3,4};
int NA=sizeof(A) / sizeof(A[0]);
int NB=sizeof(B) / sizeof(B[0]);
createlist(&La,NA,A);
printf("序列A中的元素为：");
Outputlist(La);
createlist(&Lb,NB,B);
printf("序列B中的元素为：");
Outputlist(Lb);
mergelist2(La,Lb);
printf("序列A与序列B的差为：");
Outputlist(La);
}（1）存储分配方式：
顺序存储结构用一段连续的存储单元依次存储线性表的数据元素；单链表采用链式存储结构，用一组任意的存储单元存放线性表的元素。
（2）时间性能：
查找：顺序表是一种随机存取结构，对表中任意一个结点都可以在O(1)时间内直接存取；单链表是一种顺序存取结构，对表中的结点需要从头指针顺着链查找才能取得，时间复杂度为O(n) 。
插入和删除：顺序存储结构需要平均移动表长一半的元素，时间复杂度为O(n)；单链表在计算出某位置的指针后，插入和删除的时间复杂度仅为O(1) 。
（3）空间性能：
顺序存储结构需要预先分配存储空间，分大了，容易造成空间浪费，分小了，容易发生溢出；单链表不需要预先分配存储空间，只要有就可以分配，元素个数也不受限制。
若线性表需要频繁查找，很少进行插入和删除操作时，宜采用顺序存储结构；若需要频繁插入和删除时，宜采用单链表结构。
?
?
?
cs