数据结构之线性表(顺序表）

1.1 线性表的定义

线性表（List）：零个或多个数据元素的有限序列。

在数据元素的非空有限集中，线性结构的特点：

（1）存在唯一的一个被称为“第一个”的数据元素；

（2）存在唯一的一个称为“最后一个”的数据元素；

（3）除第一个之外，集合中的每个数据元素均只有一个前驱；

（4）除最后一个之外，集合中的每个数据元素只有一个后继；

优点：可以随机访问元素

缺点：对于插入和删除元素，需要大量的位置移动

1.2 线性表的顺序表示

线性表的顺序存储结构，指的是用一段地址连续的存储单元依次存储线性表的数据元素。

来看线性表的动态分配的存储结构。

typedef ElemType int; //假设为int
#define LIST_INIT_SIZE 100 //线性表存储空间初始分配值
#define LISTINCREMENT 10 //线性表存储空间分配增量
typedef struct
{
ElemType *elem; //存储基地址
int listsize; //当前线性表存储空间分配大小
int length; //当前线性表大小
}SqList;

1.3 线性表顺序结构代码实现

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
//宏定义
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
#define LIST_INIT_SIZE 100 //线性表存储空间的初始分配量
#define LISTINCREMENT 10 //线性表存储空间的分配增量
typedef int ElemType;
typedef struct LNode
{
ElemType *elem; //存储空间基地址
int length; //线性表当前长度
int listsize; //线性表存储空间实际分配大小
}SqList;
/* 函数名称：InitList
* 函数功能：构造空的线性表
* 返回值：
* ERROR：malloc() error
* OK : 构造成功
*/
int InitList(SqList *L, int length)
{
if( 0 == length )
{
length = LIST_INIT_SIZE; //默认分配LIST_INIT_SIZE
}
L->elem = (ElemType *)malloc(sizeof(length));
if(NULL == L->elem) //空间分配失败
{
fprintf(stderr, "malloc() error.\n");
return ERROR;
}
L->listsize = length;
L->length = 0;
return OK;
}
/* 函数名称：InsertList
* 函数功能：在线性表的第i个位置插入元素e.(第i个位置，即为线性表中第i-1个元素)
* 返回值：
* ERROR：i不合法或realloc失败
* OK ：插入成功
*/
int InsertList(SqList *L, ElemType e, int i)
{
if(i < 0 || i > L->length + 1) //i不合法
{
return ERROR;
}
if(L->length >= L->listsize) //空间不足
{
ElemType *newbase = (ElemType *)realloc(L->elem, (L->listsize + LISTINCREMENT) * sizeof(ElemType));
if(!newbase)
{
return ERROR; //realloc error
}
L->elem = newbase;
L->listsize = L->listsize + LISTINCREMENT;
}
ElemType *q = &(L->elem[i]);
ElemType *p = NULL;
for(p = &(L->elem[L->length - 1]); p >= q; --p)
{
*(p + 1) = *p;
}
*q = e;
L->length++;
return OK;
}
/* 函数名称：DeleteList
* 函数功能：删除线性表第i个元素，并将其保存到e中返回
* 返回值：
* ERROR：i不合法
* OK ：删除成功
*/
int DeleteList(SqList *L, int i, ElemType *e)
{
if(i < 0 || i > L->length) //i不合法
{
fprintf(stderr, "i不合法\n");
return ERROR;
}
ElemType *q = &(L->elem[i]);
*e = *q; //获得第i个元素的值
ElemType *p = L->elem + L->length - 1;
for( ; q < p; q++) //循环左移
{
*q = *(q + 1);
}
L->length--; //当前长度减1
return OK;
}
//快速排序
int partition(SqList *L, ElemType low, ElemType high)
{
ElemType key = L->elem[low];
while(low < high) //
{
while(low < high && L->elem[high] >= key) //
{
high--;
}
L->elem[low] = L->elem[high]; //
L->elem[high] = key;
while(low < high && L->elem[low] <= key) //
{
low++;
}
L->elem[high] = L->elem[low]; //
L->elem[low] = key;
}
return low;
}
void quickSort(SqList *L, ElemType low, ElemType high)
{
ElemType key;
if(low < high)
{
key = partition(L, low, high);
quickSort(L, low, key - 1);
quickSort(L, key + 1, high);
}
}
/* 函数名称：MergeList
* 函数功能：将线性表La和线性表Lb合并到Lc中，并不删除元素
*/
int MergeList(SqList La, SqList Lb, SqList *Lc)
{
//线性表La和Lb中的元素均不递减，合并后的Lc也不递减
ElemType *pa, *pb, *pc;
Lc->listsize = La.length + Lb.length;
InitList(Lc, Lc->listsize);
Lc->length = Lc->listsize;
pa = La.elem;
pb = Lb.elem;
pc = Lc->elem;
while(pa <= &(La.elem[La.length - 1]) && pb <= &(Lb.elem[Lb.length - 1]))
{
if(*pa <= *pb)
{
*pc++ = *pa++;
}
else
{
*pc++ = *pb++;
}
}
while(pa <= &(La.elem[La.length - 1]))
{
*pc++ = *pa++;
}
while(pb <= &(Lb.elem[Lb.length - 1]))
{
*pc++ = *pb++;
}
return OK;
}
//打印线性表中元素
void printList(SqList L)
{
int i = 0;
for(i = 0; i < L.length; i++)
{
printf("%d ",L.elem[i]);
}
printf("\n");
}
int main(int argc, char **argv)
{
SqList La, Lb, Lc;
ElemType e;
int ret;
ret = InitList(&La, LIST_INIT_SIZE);
if(ret == ERROR)
{
fprintf(stderr, "InitList() error.\n");
exit(EXIT_FAILURE);
}
int data[6] = {6, 5, 8, 3, 9, 4};
int i = 0;
for(i = 0; i < 6; i++)
{
ret = InsertList(&La, data[i], i);
if(ret != OK)
{
fprintf(stderr, "插入元素失败.\n");
exit(EXIT_FAILURE);
}
}
printf("初始化后的La:\n");
printList(La);
ret = DeleteList(&La, 3, &e);
if(ret != OK)
{
fprintf(stderr, "删除元素失败.\n");
exit(EXIT_FAILURE);
}
printf("删除第3个元素后的La:\n");
printList(La);
ret = InsertList(&La, e, 3);
if(ret != OK)
{
fprintf(stderr, "插入元素失败.\n");
exit(EXIT_FAILURE);
}
printf("插入e后的La:\n");
printList(La);
//快速排序
quickSort(&La, 0, La.length - 1);
printf("排序后的La:\n");
printList(La);
printf("\n");
InitList(&Lb, LIST_INIT_SIZE);
int bdata[5] = {1, 3, 2, 4, 6};
for(i = 0; i < 5; i++)
{
InsertList(&Lb, bdata[i], i);
}
printf("初始化后的Lb:\n");
printList(Lb);
//快速排序
quickSort(&Lb, 0, Lb.length - 1);
printf("排序后的Lb:\n");
printList(Lb);
MergeList(La, Lb, &Lc);
printf("La与Lb合并后的Lc:\n");
printList(Lc);
return 0;
}

参考：严蔚敏老师之《数据结构》

梦醒潇湘love

2013-01-06 22:06

柳暗花明来真村

数据结构之线性表(顺序表）