526互联

线性表【数据结构学习-青岛大学王卓老师】

发布时间 2023-08-14 18:59:06作者: 才下眉头3

https://www.bilibili.com/video/BV1qz4y1p767/

线性表

线性表的初始化(顺序表)

Status InitList(SqList &L) {
    L.elem = (ElemType *) malloc(sizeof(ElemType) * MAXSIZE);
    if (!L.elem)
        exit(OVERFLOW);
    L.length = 0;
    return OK;
}

线性表的销毁

void DestoryList(SqList &L) {
    if (L.elem)
        free(L.elem);
    L.elem = NULL;
    L.length = 0;
}

线性表的清空

void clearList(SqList &L) {
    L.length = 0;//将线性表的长度置为0
}

线性表的长度

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

判断线性表是否为空

void isEmpty(SqList L) {
    if (L.length == 0)printf("顺序表为空");
    else printf("顺序表不为空");
}

获取元素

int GetElem(SqList L, int i, ElemType &e) {
    if (i < 1 || i > L.length)return ERROR;
    e = L.elem[i - 1];
    return OK;
}

按值查找

int LocateElem(SqList L, ElemType e) {
    for (int i = 0; i < L.length; ++i)
        if (L.elem[i] == e)return i + 1;
        return 0; //查找失败
}

插入

Status SqlInsert(SqList &L, int pos, ElemType e) {
    if (pos < 1 || pos > L.length + 1) return ERROR;
    if (L.length == MAXSIZE) return ERROR;
    for (int i = L.length - 1; i >= pos - 1; --i) {
        L.elem[i + 1] = L.elem[i];
    }
    L.elem[pos - 1] = e;
    L.length++;
    return OK;
}

删除

Status SqlDelete(SqList &L, int pos) {
    if (pos < 1 || pos > L.length) return ERROR;
    for (int i = pos - 1; i < L.length; ++i) {
        L.elem[i] = L.elem[i + 1];
    }
    L.length--;
    /*
     * for(int j =pos;j<=L.length-1;j++){
     *     L.elem[j-1] = L.elem[j];
     *     L.length--;
     *     }
     * */
    printf("删除成功\n");
}

查看顺序表

void showList(SqList L) {
    printf("顺序表如下： ");
    for (int i = 0; i < L.length; ++i) {
        printf("%2d", L.elem[i]);
    }
    putchar(10);
}

代码

好多宏定义并没有使用

这个代码写的不太好 很多地方都是返回值，可以写成输出

基本操作是这些 还有排序 反转 等

头文件SqList.h

#include <stdio.h>
#include "stdlib.h"
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
#define MAXSIZE 100
typedef int Status;
typedef int ElemType;

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

//线性表初始化
Status InitList(SqList &L);

//销毁线性表
void DestoryList(SqList &L);

//清空线性表
void clearList(SqList &L);

//线性表的长度
int GetLength(SqList L);

//判断线性表的长度是否为空
void isEmpty(SqList L);

//线性表取值
int GetElem(SqList L,int i,ElemType &e);

//按值查找
int LocateElem(SqList L,ElemType e);

//插入
Status SqlInsert(SqList &L,int pos,ElemType e);

//删除
Status SqlDelete(SqList &L,int pos);

//查看顺序表
void showList(SqList L);

main.cpp

#include "SqList.h"

int main() {
    SqList L;
    InitList(L);
    int select = 1;
    while (select) {
        printf("************************************\n");
        printf("* [1] push          [2] GetElem    *\n");
        printf("* [3] length        [4] SqlDelete  *\n");
        printf("* [5] LocateElem    [6] showList   *\n");
        printf("* [7] clearList     [8] isEmpty   *\n");
        printf("* [9] destory       [0] quit_sys   *\n");
        printf("************************************\n");
        printf("请选择:>");
        scanf("%d", &select);
        ElemType Item;
        int pos;
        if (select == 0)
            break;
        switch (select) {
            case 1:
                printf("请输入要插入的位置和数据(逗号分割):>");
                scanf("%d,%d", &pos, &Item);
                int k;
                k = SqlInsert(L, pos, Item);
                if (k == ERROR) {
                    printf("插入有误\n");
                } else {
                    printf("插入成功");
                }
                break;
            case 2:
                printf("请输入获取第几个元素\n");
                int i, j;
                scanf("%d", &i);
                j = GetElem(L, i, Item);
                if (j == ERROR) {
                    printf("查找有误\n");
                } else {
                    printf("查找到的元素为%d\n", Item);
                }
                break;
            case 3:
                printf("线性表的长度为%d\n", GetLength(L));
                break;
            case 4:
                printf("请输入要删除元素的位置:>");
                scanf("%d", &pos);
                printf("%d", SqlDelete(L, pos));
                break;
            case 5:
                printf("输入要查找的值：输出0失败\n");
                scanf("%d", &Item);
                printf("元素在第%d个位置\n", LocateElem(L, Item));
                break;
            case 6:
                showList(L);
                break;
            case 7:
                clearList(L);
                break;
            case 8:
                isEmpty(L);
                break;
            case 9:
                DestoryList(L);
                break;
            default:
                printf("输入的命令错误，请重新输入。\n");
                break;
        }
    }
    return 0;
}

SqList.cpp

#include "SqList.h"

Status InitList(SqList &L) {
    L.elem = (ElemType *) malloc(sizeof(ElemType) * MAXSIZE);
    if (!L.elem)
        exit(OVERFLOW);
    L.length = 0;
    return OK;
}

void DestoryList(SqList &L) {
    if (L.elem)
        free(L.elem);
    L.elem = NULL;
    L.length = 0;
}

void clearList(SqList &L) {
    L.length = 0;//将线性表的长度置为0
}

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

void isEmpty(SqList L) {
    if (L.length == 0)printf("顺序表为空");
    else printf("顺序表不为空");
}

int GetElem(SqList L, int i, ElemType &e) {
    if (i < 1 || i > L.length)return ERROR;
    e = L.elem[i - 1];
    return OK;
}

int LocateElem(SqList L, ElemType e) {
    for (int i = 0; i < L.length; ++i)
        if (L.elem[i] == e)return i + 1;
        return 0; //查找失败
}

Status SqlInsert(SqList &L, int pos, ElemType e) {
    if (pos < 1 || pos > L.length + 1) return ERROR;
    if (L.length == MAXSIZE) return ERROR;
    for (int i = L.length - 1; i >= pos - 1; --i) {
        L.elem[i + 1] = L.elem[i];
    }
    L.elem[pos - 1] = e;
    L.length++;
    return OK;
}

Status SqlDelete(SqList &L, int pos) {
    if (pos < 1 || pos > L.length) return ERROR;
    for (int i = pos - 1; i < L.length; ++i) {
        L.elem[i] = L.elem[i + 1];
    }
    L.length--;
    /*
     * for(int j =pos;j<=L.length-1;j++){
     *     L.elem[j-1] = L.elem[j];
     *     L.length--;
     *     }
     * */
    printf("删除成功\n");
}

void showList(SqList L) {
    printf("顺序表如下： ");
    for (int i = 0; i < L.length; ++i) {
        printf("%2d", L.elem[i]);
    }
    putchar(10);
}

单链表

单链表的初始化

void InitList_L(LinkList &L) {
    L = (LinkList) malloc(sizeof(Lnode));
    L->next = NULL;
}

链表长度

void InitList_L(LinkList &L) {
    L = (LinkList) malloc(sizeof(Lnode));
    L->next = NULL;
}

取值

void GetElem_L(LinkList L, int i, ElemType &e) {
    LinkList p;
    p = L->next;
    int j = 1;
    while (p && j < i) {
        p = p->next;
        j++;
    }
    if (!p || j > i) {
        printf("第i个元素不存在\n");
    }
    e = p->data;
}

按值查找

int LocateElem_L(LinkList L, ElemType e) {
    LinkList p;
    p = L->next;
    int j = 1;
    while (p && p->data != e) {
        p = p->next;
        j++;
    }
    if (p) {
        return j;
    } else {
        printf("表中没有该数据\n");
        return 0;
    }
}

指定位置插入

void ListInsert_L(LinkList &L, int i, ElemType e) {
    Lnode *p;
    p = L;
    int j = 0;
    while (p && (j < i - 1)) {
        p = p->next;
        j++;
    }
    if (!p || j > i - 1) {
        printf("插入位置非法\n");
    }
    Lnode *s = (Lnode*) malloc(sizeof(Lnode));
    s->data = e;
    s->next = p->next;
    p->next = s;
}

按位置删除节点

void ListDelete(LinkList &L, int i) {
    LinkList p;
    p = L;
    int j = 0;
    while (p->next && j < i-1 ) {
        p = p->next;
        j++;
    }
    if ((!p->next) || j > i-1) {
        printf("删除位置不合理;\n");
    }
    Lnode *s;
    s = p->next;
    p->next = s->next;
    free(s);
    printf("删除成功\n");
}

单链表的建立

头插法

//单链表的建立 1.头插法
void Create_Pushfront(LinkList &L, ElemType e) {
    Lnode *p = (LinkList) malloc(sizeof(Lnode));
    p->data = e;
    p->next = L->next;
    L->next = p;
}

尾插法

书上意思是按照空表进行创建

下面的代码在不是空表的时候也可以进行插入（稍微改动）

//单链表的建立 1.尾插法
void Create_Pushback(LinkList &L, ElemType e) {
    LinkList r;
    r = L;
    Lnode *p = (LinkList) malloc(sizeof(Lnode));
    p->data = e;
    p->next=NULL;
    while (r->next){
        r=r->next;
    }
    r->next=p;
    r = p;
}

查看链表

//查看链表
void show_list(LinkList L){
    Lnode *p = L->next;
    while (p){
        printf("%d-->",p->data);
        p = p->next;
    }
    putchar(10);
}

清空链表

//清空单链表
void ClearList(LinkList &L) {
    Lnode *p, *q;
    p = L->next;
    while (p) {
        q = p->next;
        free(p);
        p = q;
    }
    L->next = NULL;
}

链表销毁

//链表销毁
void DestoryList(LinkList &L) {
    Lnode *p;
    while (L) {
        p = L;
        L = L->next;
        free(p);
    }
}

以上代码按照青岛大学王卓老师

严蔚敏数据结构第二版书籍 学习

有些地方可以自行完善

可以自己写逆置 排序等等

代码

LinkList.h

#include <stdio.h>
#include "stdlib.h"

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

void InitList_L(LinkList &L);

void isEmpty(LinkList L);

void DestoryList(LinkList &L);

void ClearList(LinkList &L);

int ListLength_L(LinkList L);

void GetElem_L(LinkList L, int i, ElemType &e);

int LocateElem_L(LinkList L, ElemType e);

void ListInsert_L(LinkList &L, int i, ElemType e);

void ListDelete(LinkList &L,int i);

void Create_Pushfront(LinkList &L, ElemType e);

void Create_Pushback(LinkList &L, ElemType e);

void show_list(LinkList L);

LinkList.cpp

#include "LinkList.h"

//初始化单链表
void InitList_L(LinkList &L) {
    L = (LinkList) malloc(sizeof(Lnode));
    L->next = NULL;
}

//判断是否为空
void isEmpty(LinkList L) {
    if (L->next) {
        printf("链表不为空\n");
    } else
        printf("链表为空\n");
}

//链表销毁
void DestoryList(LinkList &L) {
    Lnode *p;
    while (L) {
        p = L;
        L = L->next;
        free(p);
    }
}

//清空单链表
void ClearList(LinkList &L) {
    Lnode *p, *q;
    p = L->next;
    while (p) {
        q = p->next;
        free(p);
        p = q;
    }
    L->next = NULL;
}

//链表长
int ListLength_L(LinkList L) {
    LinkList p;
    p = L->next;
    int i = 0;
    while (p) {
        i++;
        p = p->next;
    }
    return i;
}

//取第i个元素
void GetElem_L(LinkList L, int i, ElemType &e) {
    LinkList p;
    p = L->next;
    int j = 1;
    while (p && j < i) {
        p = p->next;
        j++;
    }
    if (!p || j > i) {
        printf("第i个元素不存在\n");
    }
    e = p->data;
}

//按值查找
int LocateElem_L(LinkList L, ElemType e) {
    LinkList p;
    p = L->next;
    int j = 1;
    while (p && p->data != e) {
        p = p->next;
        j++;
    }
    if (p) {
        return j;
    } else {
        printf("表中没有该数据\n");
        return 0;
    }
}

//第i个位置插入数据元素e
void ListInsert_L(LinkList &L, int i, ElemType e) {
    Lnode *p;
    p = L;
    int j = 0;
    while (p && (j < i - 1)) {
        p = p->next;
        j++;
    }
    if (!p || j > i - 1) {
        printf("插入位置非法\n");
    }
    Lnode *s = (Lnode*) malloc(sizeof(Lnode));
    s->data = e;
    s->next = p->next;
    p->next = s;
}

//删除第i个节点
void ListDelete(LinkList &L, int i) {
    LinkList p;
    p = L;
    int j = 0;
    while (p->next && j < i-1 ) {
        p = p->next;
        j++;
    }
    if ((!p->next) || j > i-1) {
        printf("删除位置不合理;\n");
    }
    Lnode *s;
    s = p->next;
    p->next = s->next;
    free(s);
    printf("删除成功\n");
}

//单链表的建立 1.头插法
void Create_Pushfront(LinkList &L, ElemType e) {
    Lnode *p = (LinkList) malloc(sizeof(Lnode));
    p->data = e;
    p->next = L->next;
    L->next = p;
}

//单链表的建立 1.尾插法
void Create_Pushback(LinkList &L, ElemType e) {
    LinkList r;
    r = L;
    Lnode *p = (LinkList) malloc(sizeof(Lnode));
    p->data = e;
    p->next=NULL;
    while (r->next){
        r=r->next;
    }
    r->next=p;
    r = p;
}

//查看链表
void show_list(LinkList L){
    Lnode *p = L->next;
    while (p){
        printf("%d-->",p->data);
        p = p->next;
    }
    putchar(10);
}

main.cpp

#include "LinkList.h"

int main() {
    LinkList L;
    InitList_L(L);
    int select = 1;
    ElemType Item;
    while (select) {
        printf("************************************\n");
        printf("* [1] pushfront     [2] push_back  *\n");
        printf("* [3] show_list     [4] ListDelete *\n");
        printf("* [5] pop_front     [6] GetElem_L  *\n");
        printf("* [7] isEmpty       [8] Destory_L  *\n");
        printf("* [9] ClearList     [10] Locate_L  *\n");
        printf("* [11] ListInsert   [0] quit_sys  *\n");
        printf("************************************\n");
        printf("请选择:>");
        scanf("%d", &select);
        if (select == 0)
            break;
        switch (select) {
            case 1:
                printf("请输入要插入的数据(-1结束):>");
                while (scanf("%d", &Item), Item != -1) {
                    Create_Pushfront(L, Item);
                }
                break;
            case 2:
                printf("请输入要插入的数据(-1结束):>");
                while (scanf("%d", &Item), Item != -1) {
                    Create_Pushback(L,Item);
                }
                break;
            case 3:
                show_list(L);
                break;
            case 4:
                printf("输入要删除第几个元素：");
                scanf("%d",&Item);
                ListDelete(L,Item);
                break;
            case 5:
                printf("表长为%d\n",ListLength_L(L));
                break;
            case 6:
                printf("请输入想要取值的位置\n");
                scanf("%d",&Item);
                int e;
                GetElem_L(L,Item,e);
                printf("第%d个元素为%d:\n",Item,e);
                break;
            case 7:
                isEmpty(L);
                break;
            case 8:
                DestoryList(L);
                break;
            case 9:
                ClearList(L);
                break;
            case 10:
                printf("请输入查找的元素\n");
                scanf("%d",&Item);
                printf("所在位置为%d (为0表示不存在)\n",LocateElem_L(L,Item));
                break;
            case 11:
                printf("请要插入的位置和元素\n");
                int i ;
                scanf("%d%d",&Item,&i);
                ListInsert_L(L,Item,i);
                break;
            default:
                printf("输入的命令错误，请重新输入。\n");
                break;
        }
    }
    return 0;
}

写成了菜单的形式

结构体类型的定义有多种方法

定义节点

类型

定义链表 头指针 尾指针 大小

循环链表

循环链表的特点：

  • 最后一个节点的指针域指向头节点，整个表链形成一个环
  • 由此，从表中任意节点出发，可以找到其他节点

和单链表很像，区别就是最后一个节点的next域指向头节点

带尾指针循环链表的合并

带尾指针循环链表的合并(将Tb合并在Ta之后)

p指针指向Ta的头节点p=Ta->next;Ta->next=Tb->next->next; free(Tb->next);Tb->next=p;

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

双向链表

在单链表的每个节点里再增加一个指向其直接前驱的指针域prior，这样链表中就形成了有两个方向不同的链，故称为双向链表。

双链表的定义

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

非空表

空表

双向循环链表

和单链的循环表类似，双向链表也可以有循环表

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

  • 让最后一个结点的后继指针指向头结点。

双向链表结构具有对称性

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

双向链表的插入

void ListInsert_Dul(DuLinkList &L,int i,ElemType e){
	if(!(p=GetElemP_DuL(L,i))) return ERROR;
	DuLNode *s = (DuLnode *)malloc(sizeof(DuLNode));
	s->data = e;
	s->prior = p->prior;
	p->prior->next = s;
	s->next = p;
	p->prior =s;
	return OK;
}
//GetElemP_DuL(L,i)返回第i个元素的地址

双向链表的删除

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

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

void ListDelete_DuL(DuLink &L,int i,ElemType &e){
	if(!(p = GetElem_P_DuL(L,i))) return ERROR;
	e = p->data;
	p->prior->next = p->next;
	p->next->prior = p->prior;
	free(p);
}//ListDelete_Dul

单链表、循环链表、双向链表的比较

查找 首元节点 表尾节点 节点*P的前驱节点
带头节点的点链表L L->next O(1) L->next遍历O(n) p->next 无法找到前驱
带头结点仅设头指针L的循环单链表 L->next O(1) L->next遍历O(n) p->next O(n)
带头结点仅设尾指针R的循环单链表 R->next O(1) R O(1) p->next O(n)
带头结点的双向循环链表L L->next O(1) L->prior O(1) p->prior O(1)

顺序表和链表的比较

  • 链式存储结构的优点：

    • 结点空间可以动态申请和释放
    • 数据元素的逻辑次序靠结点的指针来表示，插入和删除时不需要移动数据元素。

  • 链式存储结构的缺点：

    • 存储密度小，每个结点的指针域需额外占用存储空间。当每个结点的数据域所占字节不多时，指针域所占存储空间的比重显得很大。

    存储密度 = 结点数据本身占用的空间/结点占用的空间总量

    一般，存储密度越大，存储空间的利用率就越高。显然顺序表的存储密度为1，而链表的存储密度小于1。

    • 链式存储结构是非随机存取结构。对于任一结点的操作都要从头指针依指针链查找到该节点，增加了算法的复杂度。

线性表的应用

线性表的合并

void union(List &La,List Lb){
	La_len = ListLength(La);
	Lb_len = Listlength(Lb);
	for(int i = 1;i<=Lb_len;i++){
		GetElem(Lb,i,e);
		if(!LocateElem(La,e)) ListInsert(&La,++La_len,e);
	}
}

有序表的合并

顺序表实现

voigeList_Sq(SqList LA,SqList LB,SqLsit &LC){
	pa = LA.elem;
	pb = LB.elem;
	LC.length = LA.length + LB.length;
	LC.elem = (ElemType *)malloc(sizeof(ElemType)* MAXSIZE);
	pc = LC.elem;
	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++;
	while(pb <= pb_last) *pc++ = *pb++;
}

链表实现

void Merge_LinkedList(LinkList &La, LinkList &Lb, LinkList &Lc) {
    pa = La->next, pb = Lb->next; // pa, pb分别表示合并时所指节点
    pc = Lc = La;
    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);
}

案例分析与实现

多项式运算

typedef struct PloyNode{
    double coeffcient;
    int exponent;
    struct PloyNode* next;
}PloyNode,*PloyNomical;

同学们自己实现

基于顺序存储结构的图书信息表的排序

描述

定义一个包含图书信息（书号、书名、价格）的顺序表，读入相应的图书数据完成图书信息表的创建，然后将图书按照价格降序排序，逐行输出排序后每本图书的信息。

输入

输入n+1行，前n行是n本图书的信息（书号、书名、价格），每本图书信息占一行，书号、书名、价格用空格分隔，价格之后没有空格。最后第n+1行是输入结束标志：0 0 0（空格分隔的三个0）。其中书号和书名为字符串类型，价格为浮点数类型。

输出

总计n行，每行是一本图书的信息（书号、书名、价格），书号、书名、价格用空格分隔。其中价格输出保留两位小数。

#include<stdio.h>
#include<string.h>
#include<malloc.h>
#include<stdlib.h>
#define MAXSIZE 10000//图书表可能达到的最大长度
#define OK 1
#define ERROR 0
#define OVERFLOW -2

typedef int Status;

typedef struct //图书信息定义
{
    char  no[20];//图书ISBN
    char  name[50];//图书名字
    float price;//图书价格
}Book;

typedef struct
{
    Book *elem;//存储空间的基地址
    int  length;//图书表中当前图书个数
}SqList;//图书表的顺序存储结构类型为SqList



Status InitList_Sq(SqList &L)//构造一个空的顺序表
{
    L.elem=(Book * )malloc(MAXSIZE * sizeof(Book));//为顺序表分配一个大小为MAXSIZE的数组空间
    if(!L.elem) exit(OVERFLOW);//存储失败
    L.length=0;//空表长度为零
    return OK;
}

Status PrintList_Sq(SqList &L)
{
    for(int i=0;i<L.length;i++)     //顺序输出每本书的信息
    {
        printf("%s %s %.2f\n", L.elem[i].no,L.elem[i].name,L.elem[i].price);//每本书信息
        // printf("%.2f\n",L.elem[i].price);//保留两位小数
    }
    return OK;                      //OK=1，返回真
}

Status CreationList_Sq(SqList &L,char *no,char *name,float price)
{
    Book B;                    //定义B为Book
    strcpy(B.no,no);       //复制书号
    strcpy(B.name,name);
    B.price=price;
    L.elem[L.length]=B;         //l的elem数组存储书的信息
    L.length++;                 //每存好一本书，书总量自加1,l.length=l.length+1.单目运算
    return OK;
}
Status B_Sort(SqList &L){
    for (int i = 0; i <L.length ; ++i) {
        for (int j = 0; j < L.length -1 -i; ++j) {
            if (L.elem[j].price<L.elem[j+1].price){
                Book temp = L.elem[j];
                L.elem[j]=L.elem[j+1];
                L.elem[j+1] = temp;
            }
        }
    }
}
int main()
{

    char no[20],name[50];
    float price;
    SqList L;
    InitList_Sq(L);
    while(scanf("%s %s %f",no,name,&price))
    {
        if(!strcmp(no,"0")&&!strcmp(name,"0")&&price==0.0)
            break;
        CreationList_Sq(L,no,name,price);
    }
    B_Sort(L);
    PrintList_Sq(L);
    return 0;
}