2022-09-07
概述 Overview
1. 线性结构的定义
若结构是非空有限集，则有且仅有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前趋和一个直接后继
(a0, a1, ... , an-1)
2. 线性结构的特点
. 只有一个首结点和尾结点
. 除首尾结点外，其他结点只有一个直接前驱和一个直接后继
3. 常见的线性结构
线性表 linear list
堆栈 stack
队列 queue
字符串 string
数组 array
4. 线性表的现实体现
. 排队（核酸检测、打饭、银行办理业务、买奶茶、公园检票、文件打印）
. 函数的调用
. 多项式的使用
. 各种管理系统和平台
5. 线性表的抽象数据类型ADT
. 数据对象
D={ ai | ai∈Set, i=0,1,2,...,n-1}
. 数据关系
R={<ai, ai+1> | ai,ai+1∈Set, i=0,1,2,...,n-2}
. 数据运算
init(&list) 初始化
clear(&list) 清空
destroy(&list) 销毁
isEmpty(&list) 是否为空
length(&list) 表长度
insertAt(&list, ind, el) 插入
get(&list, ind, &el) 获取元素
locate(&list, el) 获取元素索引
delAt(&list,ind) 删除指定位置的元素
delEl(&list,el) 删除指定元素
update(&list, ind, el) 更新指定位置元素
toString(&list) 输出
traverse(&list) 遍历
[Section End]
顺序表 Sequence List
1. 顺序表的存储
定义：把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构
方法：用一组地址连续的存储单元依次存储线性表的元素，通过数组来实现
特点：访问效率高：邻近存储；修改效率低：增加和删除需要移动大量数据节点
2. 顺序表的存储结构
<- length ->
a0 a1 ... ai
<- MaxSize ->
3. 顺序表的数据结构
//伪代码
#define MaxSize 20

typedef struct
{
    elementType *data;
    int len;
}List;
//实际代码
#define MaxSize 20

typedef struct
{
    int *data;
    int len;
}List;
4. 顺序表的基本操作
4.0 几点说明
.函数的返回类型
.异常的处理
4.1 初始化
创建一个总长度为MaxSize的空数组；
内存管理：如何申请空间??
参数传递：如何把地址传出来???
//[代码1]
int Init(List *list)
{    
    list->data = (int *)malloc(sizeof(int) * MaxSize);
    if (list->data)
    {
        list->len = 0;
        return 0;
    }
    else
    {
        return -1;
    }
}
//[代码2]
int Init(List *list)
{    
    list->data = (int *)malloc(sizeof(int) * MaxSize);
    if (!list->data)
    {
        return -1;
    }
    list->len = 0;
}
//[代码3]
int Init(List *list)
{
    list->data = (int *)malloc(sizeof(int) * MaxSize);
    if (list->data)
    {
        list->len = 0;
        return 0;
    }
    return -1;
}
//[代码4]
int Init(List *list)
{
    list->data = (int *)malloc(sizeof(int) * MaxSize);
    return list->data ? list->len : -1;
}
//[代码5]
void Init(List *list)
{
    list->data = (int *)malloc(sizeof(int) * MaxSize);
    if (!list->data)
    {
        printf("init fail\n");
        return;
    }
    list->len = 0;
    printf("init ok\n");
}
4.2 赋值assign
为线性表的某个或某些元素赋值； 
//利用数组名和地址偏移量赋值
*(list->data +i) = val;
//利用数组元素索引赋值
list->data[i] = val;
//利用数组对线性表整体赋值
void assign(List *list, int arr[], int len)
{
    int i;
    for (i = 0; i < len; i++)
    {
        list->data[i] = arr[i];
        list->len++;
    }
}
//利用输入scanf对线性表整体赋值
4.3 读getAt
根据位置/索引index取值el；
取到的值如何传递出去?
//赋值出去
void getAt(List *list, int ind, int *res)
{
    if (ind < 0 || ind > list->len - 1)
    {
        printf("get-index overfollow.\n");
        return;
    }
    *res = list->data[ind];
}
//return出去
int getAt(List *list, int ind)
{
    if (ind < 0 || ind > list->len - 1)
    {
        return -1;
    }
    return list->data[ind];
}
4.4 插入insertAt
在线性表某个位置插入元素；
头插?尾插?
void insertAt(List *list, int ind, int el)
{
    if (ind < 0 || ind > list->len || ind > MaxSize)
    {
        printf("insert-index overfollow\n");
        return;
    }
    int i;
    for (i = list->len; i > ind; i--)
    {
        list->data[i] = list->data[i - 1];
    }
    list->data[ind] = el;
    list->len++;
}
4.5 删除delAt
删除线性表的元素；
需不需要返回被删除的元素?
void delAt(List *list, int ind, int *el)
{
    if (ind < 0 || ind > list->len)
    {
        printf("del-index overfollow\n");
        return;
    }
    *el = list->data[ind];
    int i;
    for (i = ind; i < list->len; i++)
    {
        list->data[i - 1] = list->data[i];
    }
    list->len--;
}
[思考]删除前和删除后，最后一个元素有什么变化?
4.6 输出
显示/遍历线性表的元素；
如何个性化?
如何更直观?
void tranverse(List *list)
{
    int i;    
    for (i = 0; i < list->len; i++)
    {
        printf("%d\t", list->data[i]);
    }    
}
void tranverse(List *list)
{
    int i;
    for (i = 0; i < list->len; i++)
    {
        printf("%d\t", i);
    }
    printf("\n");
    for (i = 0; i < list->len; i++)
    {
        printf("%d\t", list->data[i]);
    }
    printf("\n");
    printf("-----------------------\n");
}
5. 顺序表参考代码
#include <stdio.h>
#include <stdlib.h>

#define MaxSize 5
typedef struct
{
    int *data;
    int len;
} List;

void Init(List *list)
{
    list->data = (int *)malloc(sizeof(int) * MaxSize);
    if (!list->data)
    {
        printf("init fail\n");
        return;
    }
    list->len = 0;
    printf("init ok\n");
}

void assign(List *list, int arr[], int len)
{
    int i;
    for (i = 0; i < len; i++)
    {
        list->data[i] = arr[i];
        list->len++;
    }
}

void tranverse(List *list)
{
    int i;
    for (i = 0; i < list->len; i++)
    {
        printf("%d\t", i);
    }
    printf("\n");
    for (i = 0; i < list->len; i++)
    {
        printf("%d\t", list->data[i]);
    }
    printf("\n");
    printf("--------------------------------------------------\n");
}

void getAt(List *list, int ind, int *res)
{
    if (ind < 0 || ind > list->len - 1)
    {
        printf("get-index overfollow.\n");
        return;
    }
    *res = list->data[ind];
}

void insertAt(List *list, int ind, int el)
{
    if (ind < 0 || ind > list->len || ind > MaxSize)
    {
        printf("insert-index overfollow\n");
        return;
    }
    int i;
    for (i = list->len; i > ind; i--)
    {
        list->data[i] = list->data[i - 1];
    }
    list->data[ind] = el;
    list->len++;
}

void delAt(List *list, int ind, int *el)
{
    if (ind < 0 || ind > list->len)
    {
        printf("del-index overfollow\n");
        return;
    }
    *el = list->data[ind];
    int i;
    for (i = ind; i < list->len; i++)
    {
        list->data[i - 1] = list->data[i];
    }
    list->len--;
}

int main(int argc, char *argv[])
{
    int i, res;

    List list;

    Init(&list);

    int val[10] = {10, 23, 4, 56, 26};
    assign(&list, val, 5);

    tranverse(&list);

    getAt(&list, 3, &res);

    insertAt(&list, 2, 11);
    tranverse(&list);
    delAt(&list, 2, &res);
    tranverse(&list);

    return 0;
}
[Section End]
链式表 Linked List
1. 链式表的存储
. 逻辑上相邻；存储上随意
. 存取效率低：只能通过头指针进入链表，根据每个结点的指针域访问其它结点：顺藤摸瓜/顺序存取法
. 修改效率高：节点增加、删除操作，只需要修改链接指针，不必移动数据
. 头指针：链表由头指针唯一确定； 不要弄丢头指针； 不要掉链子
. 存储密度小
2. 链式表的存储结构
. 除了数据元素外，借助指针实现数据之间的逻辑关系
. 根据指针的多少和指向，可以细分：单链表、双向链表、循环链表等
. 带头节点的单链表：为方便操作，通常在数据节点之前增加一个头节点，用来表示该链表；链表由指向头节点的头指针唯一确定
. 节点分类：头节点、数据节点[首节点、尾节点]
3. 单链表的数据结构
//节点和链表共享一个数据结构
typedef struct LNode
{
    int data;
    struct LNode *next;
} Node, List;
//节点和链表单独定义数据结构
typedef struct node
{
    int data;
    struct node *next;
} Node;

typedef struct
{
    Node *head;
    int n;
} LinkList;
4. 单链表的基本操作
4.1 初始化Init
创建一个带有头节点的空链表；
Node *Init() {
    Node *head=(Node *)malloc(sizeof(Node));
    printf("%p\n",head);
    head->next=NULL;
    return head;
}
Status Init(List *list)
{
    *list = (List *)malloc(sizeof(Node));
    printf("insider %p\n", *list);
    if (!(*list))
    {
        return ERROR;
    }
    (*list)->next = NULL;
    return OK;
}
4.2 遍历Display
遍历链表，个性化输出每个节点数据；
void Display(List *list) {
    Node *head=list->next;
    while(head) {
        printf("%d\t",head->data);
        head=head->next;
    }
    printf("\n");
}
void Display(List *list){
    printf("List->");
    Node *head=list->next;
    while(head){
        printf("%d->",head->data);
        head=head->next;
    }
    printf("NULL\n");
}
4.3 插入Insert
头插：在链表头部插入数据节点；
void InsertHead(List *list,int data) {
    Node *p=list;
    Node *node=(Node *)malloc(sizeof(Node));
    node->data=data;
    node->next=p->next;
    list->next=node;
}
尾插：在链表尾部部插入数据节点；
void InsertTail(List *list,int data){
Node *p=list->next;
while(p->next){
    p=p->next;
}	
Node *node=(Node *)malloc(sizeof(Node));
node->data=data;
node->next=NULL;
p->next=node;
}
在链表指定位置插入数据节点；
void InsertByIndex(List *list, int ind, int data)
{
    int i = 0;
    List *p = list;
    if (ind < 0 || ind > Len(list) - 1)
    {
        printf("index overfollow\n");
        return;
    }
    while ( i < ind)
    {
        p = p->next;
        i++;
    }
    Node *node = (List *)malloc(sizeof(Node));
    node->data = data;
    node->next = p->next;
    p->next = node;   
}
[]
. 获取插入位置的前一个位置；
. 头插、尾插是插入的特例；
4.4 表长Len
获取链表数据节点的个数；
int Len(List *list) {
    int len=0;
    Node *p=list->next;
    while(p) {
        len++;
        p=p->next;
    }
    return len;
}
4.5 获取元素Get
根据指定位置获取链表数据节点；
void Get(List *list,int ind,int *res) {
    int i=0;
    int length=Len(list);
    if( ind<0 || ind>length-1 ) {
        printf("index overfollow\n");
        return;
    }
    Node *p=list->next;
    while(inext;
        i++;
    }
    *res=p->data;
}
4.6 元素索引IndexOf
获取数据节点在链表中的位置；
int IndexOf(List *list, int data)
{
    int i = 0;
    Node *p = list->next;
    while (p && p->data != data)
    {
        p = p->next;
        i++;
    }
    return p?i:-1;
}
4.7 删除Delete
根据指定位置删除链表中的数据节点；
void DeleteByIndex(List *list, int ind, int *res)
{
    int i = 0;
    Node *p = list,*q;
    if (ind < 0 || ind>Len(list)-1)
    {
        printf("index overfollow\n");
        return;
    }
    while (p->next && i < ind)
    {
        printf("%d\t",i);
        p = p->next;
        i++;
    }
    q = p->next;
    *res = q->data;
    p->next = q->next;
    free(q);
}
[]
1. 为什么要使用2个指针?
2. 如何删除指定元素?
3. 如何利用IndexOf函数删除指定元素?
[]
free()的节点必须通过malloc()申请的节点；即：如果节点是手动创建的，则无法free()，会导致函数结束异常；
4.9 其它函数
根据业务需要，封装其它功能函数；
5. 单链表参考代码
    //头文件
    #include <stdio.h>
    #include <stdlib.h>

    typedef struct node
    {
        int data;
        struct node *next;
    } Node, List;
    
    int Len(List *list);
    Node *Init()
    {
        Node *head = (Node *)malloc(sizeof(Node));
        printf("%p\n", head);
        head->next = NULL;
        return head;
    }
    
    void Display(List *list)
    {
        printf("List->");
        Node *head = list->next;
        while (head)
        {
            printf("%d->", head->data);
            head = head->next;
        }
        printf("NULL\n");
    }
    
    void InsertHead(List *list, int data)
    {
        Node *p = list;
        Node *node = (Node *)malloc(sizeof(Node));
        node->data = data;
        node->next = p->next;
        p->next = node;
    }
    void InsertTail(List *list, int data)
    {
        Node *p = list;
        while (p->next)
        {
            p = p->next;
        }
        Node *node = (Node *)malloc(sizeof(Node));
        node->data = data;
        node->next = NULL;
        p->next = node;
    }
    void InsertByIndex(List *list, int ind, int data)
    {
        int i = 0;
        List *p = list;
        if (ind < 0 || ind > Len(list) - 1)
        {
            printf("index overfollow\n");
            return;
        }
        while (i < ind)
        {
            p = p->next;
            i++;
        }
        Node *node = (List *)malloc(sizeof(Node));
        node->data = data;
        node->next = p->next;
        p->next = node;
    }
    
    int Len(List *list)
    {
        int len = 0;
        Node *head = list->next;
        while (head)
        {
            len++;
            head = head->next;
        }
        return len;
    }
    
    void Get(List *list, int ind, int *res)
    {
        int i = 0;
        int length = Len(list);
        if (ind < 0 || ind > length - 1)
        {
            printf("index overfollow\n");
            return;
        }
        Node *p = list->next;
        while (i < ind)
        {
            p = p->next;
            i++;
        }
        *res = p->data;
    }
    
    int IndexOf(List *list, int data)
    {
        int i = 0;
        Node *p = list->next;
        while (p && p->data != data)
        {
            p = p->next;
            i++;
        }
        return p ? i : -1;
    }
    
    void DeleteByIndex(List *list, int ind, int *res)
    {
        int i = 0;
        int length = Len(list);
        Node *p = list;
        Node *q = NULL;
        if (ind < 0 || ind > length - 1)
        {
            printf("index overfollow\n");
            return;
        }
        while (p->next && i < ind)
        {
            printf("%d\t", i);
            p = p->next;
            i++;
        }
        q = p->next;
        *res = q->data;
        p->next = q->next;
        free(q);
    }
    //主文件
    #include <stdio.h>
    #include <stdlib.h>
    #include "demo.h"
    
    int Len(List *list);
    int main(int argc, char *argv[])
    {
        int res,tmp;
        List *list = Init();
        InsertHead(list, 10);
        InsertHead(list, 20);
        InsertHead(list, 30);
        Display(list);
        res = Len(list);
        printf("len=%d\n", res);
        Get(list, 5, &res);
        printf("get res=%d\n", res);
        Display(list);
        InsertTail(list, 190);
        InsertTail(list, 180);
        InsertTail(list, 170);
        // InsertHead(list,10);
        InsertByIndex(list, 2, 222);
        Display(list);
        InsertByIndex(list, 5, 222);
        Display(list);
        tmp = 222;
        res = IndexOf(list, tmp);
        printf("index of %d is %d\n", tmp, res);
        tmp = 8;
        res = IndexOf(list, tmp);
        printf("index of %d is %d\n", tmp, res);
        tmp = 7;
        DeleteByIndex(list, tmp, &res);
        printf("delete index of %d \n", res);
        Display(list);
        return 0;
    }
[Section End]
应用 Application
1. 通信录
项目效果请参照 通信录
参考代码；contact.h为定义的数据结构，请参照前面的数据结构和算法，根据实际情况灵活调整；
    #include <stdio.h>
    #include <stdlib.h>
    #include "contact.h"
    
    void menu(void);
    
    int main(void)
    {
    int option, len;
    printf("\nWelcome\n");
    Contact *contact = Init();
    do
    {
        menu();
        printf("Please make a choice->>>");
        scanf("%d", &option);
        switch (option)
        {
        case Add:
            AddByHead(contact);
            break;
        case Delete:
            DeleteByIndex(contact);
            break;
        case Update:
            UpdateByIndex(contact);
            break;
        case Search:
            SearchByName(contact);
            break;
        case Print:
            Display(contact);
            break;
        case Sort:
            SortByAge(contact);
            break;
        case Output:
            OutputToFile(contact);
            break;
        case LengthOfContact:
            len = Length(contact);
            printf("lenght of current contact is %d\n", len);
            printf("%s %s\n\n", __TIME__, __DATE__);
            break;
        case AddByTail:
            OutputToFile(contact);
            break;
        case Exit:
            printf("Bye Bye\n");
            printf("%s %s\n\n", __TIME__, __DATE__);
            exit(0);
            break;
        default:
            printf("Bye Bye\n");
            printf("%s %s\n\n", __TIME__, __DATE__);
            exit(0);
            break;
        }
    } while (1);

    return 0;
}
void menu(void)
{
    printf("**********************************************\n");
    printf("***   1.Insert                2.Delete     ***\n");
    printf("***   3.Update                4.Search     ***\n");
    printf("***   5.Display               6.Sort       ***\n");
    printf("***   7.Output                8.Length     ***\n");
    printf("***   9.InsertByTail          0.Exit       ***\n");
    printf("**********************************************\n");
    printf("<<<<<<<<<<<<<202012000001张树彬>>>>>>>>>>>>>\n\n");
}
2. 多项式加法
    #include <stdio.h>
    #include <stdlib.h>

    typedef struct pNode
    {
        int coef;
        int exp;
        struct pNode *next;
    } pNode;
    
    typedef struct
    {
        struct pNode *head;
    } PolyExp;
    
    void createPlyExp(PolyExp *pe)
    {
        pe->head = (pNode *)malloc(sizeof(pNode));
        pe->head->exp = -1;
        pe->head->next = NULL;
        pNode *pn, *pre, *p;
        while (1)
        {
            pn = (pNode *)malloc(sizeof(pNode));
            printf("conf:\n");
            scanf("%d", &pn->coef);
            printf("exp:\n");
            scanf("%d", &pn->exp);
            if (pn->exp < 0)
            {
                break;
            }
            pre = pe->head;
            p = pre->next;
            // 已有数据大于新数据，后移
            while (p && p->exp > pn->exp)
            {
                pre = p;
                p = p->next;
            }
            pn->next = p;
            pre->next = pn;
        }
    }
    
    void displayPolyExp(PolyExp *pe)
    {
        pNode *pn;
        pn = pe->head->next;
        while (pn)
        {
            printf("%dx^%d ", pn->coef, pn->exp);
            pn = pn->next;
        }
        printf("\n");
    }
    
    void addPolyExp(PolyExp *pe0, PolyExp *pe1)
    {
        pNode *pre0 = pe0->head;
        pNode *p0 = pe0->head->next;
        pNode *pre1 = pe1->head;
        pNode *p1 = pe1->head->next;
        pNode *tmp;
        while (p0 && p1)
        {
            while (p1)
            {
                if (p1->exp > p0->exp)
                {
                    printf(">\n");
                    // p1不掉链
                    pre1->next = p1->next;
                    // 移动p1的节点到p0里
                    p1->next = p0;
                    pre0->next = p1;
                    p1 = pre1->next;
                    // 因为p0加入了一个节点，所以要更新p0的指针域：p0不用动，pre0前移一个节点
                    pre0 = pre0->next;
                }
                else if (p1->exp == p0->exp)
                {
                    printf("=\n");
                    // 系数相加
                    p0->coef = p0->coef + p1->coef;
                    // p1不掉链
                    pre1->next = p1->next;
                    tmp = p1;
                    // 释放空间
                    free(tmp);
                    p1 = pre1->next;
                }
                else if (p1->exp < p0->exp)
                {
                    printf("<\n");
                    break;
                }
            }
            pre0 = p0;
            p0 = p0->next;
        }
    }
    int main()
    {
        PolyExp *pe0, *pe1;
        pe0 = (PolyExp *)malloc(sizeof(PolyExp));
        pe1 = (PolyExp *)malloc(sizeof(PolyExp));
        createPlyExp(pe0);
        displayPolyExp(pe0);
        createPlyExp(pe1);
        displayPolyExp(pe1);
        addPolyExp(pe0, pe1);
        printf("res\n");
        displayPolyExp(pe0);
        return 0;
    }
[Section End]