线性表
线性表的顺序表示和实现
//线性表的动态分配顺序存储结构
#define LIST_INIT_SIZE 100 //线性表存储空间的初始分配量
#define LISTINCREMENT 10 //分配增量
typedef struct {
ElemType * elem; //存储空间基址
int length; //当前长度
int listsize; //当前分配的存储容量(以sizeof(ElemType)为单位)
}SqList;
Status InitList_Sq(SqList &L) {
//构造一个空的线性表L
L.elem = (ElemType * ) malloc (LIST_INIT_SIZE * sizeof(ElemType));
if(!L.elem) exit(OVERFLOW); //存储分配失败
L.length = 0; //空表长度为0
L.listsize = LIST_INIT_SIZE; //初始存储容量
return OK;
}
Status ListInset_Sq(SqList &L, int i, ElemType e) {
//在顺序线性表L中第i个位置之前插入新的元素e
//i的合法值为 1 <= i <= ListLength_Sq(L) + 1
if( i < 1 || i L.length + 1) return ERROR; //i值不合法
if(L.Length >= L.listsize) { //当前存储空间已满,增加分配
newbase = (ElemType * ) realloc(L.elem, (L.listsize + LISTINCREMENT) * sizeof(ElemType));
if(!newbase) exit(OVERFLOW); //存储分配失败
L.elem = newbase; //新基址
L.listsize += LISTINCREMENT; //增加存储容量
}
q = & (L.elem[i-1]); //q为插入位置
for(p = &(L.elem[L.length-1]); p >= q; --p)
*(p + 1) = *p; //插入位置及之后的元素右移
*q = e; //插入e
++L.length; //表长加一
return Ok;
}
Status ListDelete_Sq(SqList &L, int i, ElemType &e) {
//在顺序表L中删除第i个元素,并用e返回其值
//i的合法值为 1 <= i <= ListLength_Sq(L)
if(i < 1 || i > L.length) return ERROR;
p = & (L.elem[i-1]); //p为被删除元素的位置
e = *p;
q = L.elem + L.length - 1; //表尾元素的位置
for(++p; p <= q; ++p)
*(p - 1) = *p; //被删除元素之后的元素左移
--L.length; //表长减一
return OK;
}
void MergeList_Sq(SqList La, SqList Lb, SqList &Lc) {
//已知顺序线性表La和Lb中的元素按值非递减排列
//归并La Lb到顺序线性表Lc,Lc的元素值也按值非递减排列
pa = La.elem; pb = Lb.elem;
Lc.listsize = Lc.length = La.length + Lb.length;
pc = Lc.elem = (ElemType * ) malloc (Lc.listsize * sizeof(ElemType));
if(!Lc.elem) exit(OVERFLOW); //存储分配失败
pa_last = La.elem + La.length - 1;
pb_last = Lb.elem + Lb.length - 1;
while(pa <= pa_last && pb <= pb_last) { //归并
if( * pa <= * pb) * pc++ = * pa++;
else * pc++ = * pb++;
}
while(pa <= pa_last) * pc++ = * pa++; //插入La中剩余元素
while(pb <= pb_last) * pc++ = * pb++;
}
线性表的链式表示和实现
//线性表的单链表存储结构
typedef struct LNode {
ElemType data;
Struct LNode *next;
}LNode, *LinkList;
Status GetElem_L(LinkList L, int i, ElemType &e) {
// L为带头结点的单链表的头指针
// 当第i个元素存在时,其值赋给e并返回OK,否则返回ERROR
p = L -> next; j = 1; //初始化,p指向第一个结点,j为计数器
while(p && j < i) { //顺时针向后查找,直到p指向第i个元素或p为空
p = p -> next; ++j;
}
if(!p || j > i) return ERROR; //第i个元素不存在
e = p -> data; //取第i个元素
return OK;
}
Status ListInsert_L(LinkList &L, int i, ElemType e) {
// 在带头结点的单链线性表L中第i个位置之前插入元素e
p = L; j = 0;
while(p && j < i - 1) { // 寻找第i-1个结点
p = p -> next;
++j;
}
if(!p || j > i-1) return ERROR; // i小于1或者大于表长加1
s = (LinkList) malloc (sizeof(LNode)); //生成新结点
s -> data = e; s -> next = p -> next;
p -> next = s;
return OK;
}
Status ListDelete_L(LinkList &L, int i, ElemType &e) {
// 在带头结点的单链线性表L中,删除第i个元素,并由e返回其值
p = L; j = 0;
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;
}
void CreateList_L(LinkList &L, int n) {
// 逆位序输入n个元素的值,建立带表头结点的单链线性表L
L = (LinkList) malloc (sizeof(LNode));
L -> next = NULL; // 先建立一个带头结点的单链表
for(i = n; i > 0; --i) {
p = (LinkList) malloc (sizeof(LNode)); // 生成新结点
scanf(&p -> data); // 输入元素值
p -> next = L -> next; L -> next = p; // 插入到表头
}
}
// 对比着顺序线性表的归并理解
void MergeList_L(LinkList &La, LinkList &Lb, LinkList &Lc) {
// 已知单链线性表La和Lb的元素按值非递减排列
// 归并La和Lb得到新的单链线性表Lc, Lc的元素也按值非递减排列
pa = La -> next; pb = Lb -> next;
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的头结点
}
双向链表
// 线性表的双向链表存储结构
typedef struct DuLNode {
ElemType data;
struct DuLNode *prior;
struct DuLNode *next;
}DuLNode, *DuLinkList;
Status ListInsert_DuL(DuLinkList &L, int i, ElemType e) {
// 在带头结点的双链循环线性表L中第i个位置之前插入元素e
// i的合法值为 1<=i<=表长+1
if(!(p = GetElemP_DuL(L, i))) // 在L中确定插入位置
return ERROR; // p=NULL 插入位置不合法
if(!(s = (DuLinkList) malloc (sizeof(DuLNode)))) return ERROR;
s -> data = e;
s -> prior = p -> prior; p -> prior -> next = s;
s -> next = p; p -> prior = s;
return OK;
}
Status ListDelete_DuL(DuLinkList &L, int i, ElemType &e) {
// 删除带头结点的双链循环线性表L的第i个元素,i的合法值为1<=i<=表长
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;
}
题集例题
2.10 从顺序存储结构的线性表a中删除第i个元素起的k个元素
Status DeleteK {SqList &a, int i, int k)
{
if(i < 1 || i > a.length - 1 || k < 0 || k > a.length - i) //注意i的编号从0开始
return INFEASIBLE;
for(j = 0; j < k; j++)
a.elem[i+j] = a.elem[i+K+j];
a.length = a.length - k;
return OK;
}
2.11 设顺序表va中的数据元素递增有序。试写一算法,将x插入到顺序表的适当位置上,以保持该表的有序性。
Status InsertOrderList(SqList &va, ElemType x)
{
int i;
if(va.length == va.listsize) return(OVERFLOW);
for(i = va.length; i > 0, x < va.elem[i-1]; i--)
va.elem[i] = va.elem[i-1];
va.elem[i] = x;
va.length++;
return OK;
}
2.19 已知线性表中的元素以值递增有序排列,并以单链表作存储结构。试写一高效的算法,删除表中所有值大于mink且小于maxk的元素(若表中存在这样的元素),同时释放被删结点空间,并分析你的算法的时间复杂度(注意,mink和maxk是给定的两个参变量,它们的值可以和表中的元素相同,也可以不同)。
Status Delete_Between(Linklist &L, int mink, int maxk)
{
p = L;
while(p->next->data <= mink)
p = p -> next; // p是最后一个不大于mink的元素
if(p->next) // 如果还有比mink更大的元素
{
q = p -> next;
while(q->data < maxk)
q = q -> next; // q是第一个不小于maxk的元素
p -> next = q;
}
return OK;
}
2.21 试写一算法,实现顺序表的就地逆置,即利用原表的存储空间将线性表倒置。
Status ListReverse_Sq(SqList &L)
{
int i;
ElemType x;
for(i = 0; i < l.length/2; i++)
{
x = L.elem[i];
L.elem[i] = L.elem[L.length-1-i];
L.elem[L.length-1-i] = x;
}
return OK;
}
2.22 试写一算法,对单链表实现就地逆置。
Status ListReverse_L(LinkList &L)
{
LinkList p,q;
p = L -> next;
L -> next = NULL;
while(p){
q = p;
p = p -> next;
q -> next = L -> next;
L -> next = q;
}
return OK;
}
2.25 假设以两个元素依值递增有序排列的线性表 A和 B 分别表示两个集合(即同一表中的元素 值各不相同) ,现要求另辟空间构成一个线性表 C,其元素为 A 和 B中元素的交集,且表 C中的 元素依值递增有序排列。试对顺序表编写求 C的算法。
Status SqList_Insert(SqList A, SqList B, SqList &C)
{
int i = 1, j = 1, k = 0;
while(A.elem[i] && B.elem[j])
{
if(A.elem[i] < B.elem[j]) i++;
if(A.elem[i] > B.elem[j]) j++;
if(A.elem[i] = B.elem[j]) {
C.elem[k++] = B.elem[j];
i++; j++;
}
}
return OK;
}