您好,欢迎访问代理记账网站
  • 价格透明
  • 信息保密
  • 进度掌控
  • 售后无忧

第二章—线性表

线性表

  • 线性表的基本概念和实现
    • 线性表的定义
    • 线性表的逻辑特性
    • 线性表的存储结构
    • 常见问题
  • 线性表的结构体定义和基本操作
    • 线性表的结构体定义
    • 顺序表的操作
    • 单链表的操作
    • 双链表的操作
    • 循环链表的操作
  • 逆置问题

线性表的基本概念和实现

线性表的定义

线性表是具有相同特性数据元素的一个有限序列。该序列中所含元素的个数叫做线性表的长度,用n表示。注意:n可以等于0,表示线性表是一个空表。

线性表是一种简单的数据结构,可以把它想象成一队学生。学生人数对应线性表的长度,学生人数是有限的,这里体现了线性表是一个序列;队中所有人的身份是学生,体现了线性表中的元素都是相同的特性;线性表可以是有序的,也可以是无序的,如果学生按照身高排队,则体现了线性表的有序性。

线性表的逻辑特性

在一队学生中,只有一个学生在队头,同样也只有一个学生在队尾,在队头的学生前面没有其他学生,在队尾的学生后边没有其他学生,除了队头和队尾的学生之外,其他的学生有一个前驱,同时也有一个后继。线性表也是如此,只有一个表头元素,只有一个表尾元素,表头元素没有前驱,表尾元素没有后继,其他的元素有一个前驱和一个后继。

线性表的存储结构

线性表的存储结构有顺序存储结构和链式存储结构两种,前者称为线性表,后者称为链表。下面对比两种存储结构

  1. 顺序表:就是把线性表中的所有元素按照其逻辑顺序,一次存储到从指定的存储位置开始的一块连续的存储空间中。这样,线性表中第一个元素的存储位置就是指定的存储位置,第i+1个元素紧接在第i个元素的存储位置的后面。
  2. 链表:每个节点不仅包含所存元素的信息,还包含元素之间逻辑关系的信息,如单链表中前驱节点包含后继节点的地址信息,这样就可以通过前驱节点中的地址信息找到后继节点的位置。

两种存储结构的比较

  • 顺序表就好像一排房间,每个房间的门牌号就是该房间到0点的距离,房间长度为1,因此只要知道0点的位置,然后通过房间号就可以马上找到任何一个房间。这就是顺序表的第一个特性—随机访问特性;房间都是紧挨着的,即连续占用了一片空间,并且房间所占空间的数量是确定的,并且不会减少,也不会增大,这就是顺序表的第二个特性,即顺序表要求占用连续的存储空间,存储空间只能预先分配好,一旦分配好,对其操作时始终不变。在插入操作时,顺序表需要移动多个元素。(因为空间已经固定,所以插入时,必须将其后面的元素依次往后移动)
  • 链表中,元素节点散落存在在存储空间中,每个节点都有下一个节点的地址,按照这个地址,可以依次找到链表中的每一个节点,但是只有知道前一个节点的内容,才可以找到下一个节点,所以链表不支持随机访问。链表中每一个节点需要划分一部分空间存储下一个节点的指针,因此链表的存储空间利用率较顺序表稍低一些。链表中当前节点的位置是由其前驱节点中的地址信息所指示的,而不是由其相对于初始位置的偏移量来确定。因此,链表的节点可以散落在内存中的任意位置,且不需要一次性地划分所有节点所需的空间给链表。而是需要几个节点临时划分几个。由此可见,链表的内存支持动态分配。在插入时,无须移动元素。

链表有5种形式

  1. 单链表:在每个节点中除了包含数据域外,还包含指针域,用以指向后继节点。这里还要区分一下带头结点的单链表和不带头结点的单链表。
    1. 带头结点的单链表中,头指针head指向头结点,头结点的值域不含任何信息,从头结点的后继节点开始存储数据信息,头指针始终不等于NULL,head->next等于NULL的时候,链表为空。
    2. 不带头结点的单链表中的头指针head直接指向开始节点。当head为NULL时,链表为空。
  2. 双链表:单链表只能由开始节点走到终端节点,而不能由终端结点反向走到开始节点,如果要求输出从终端结点到开始节点的数据序列,对于单链表来说很麻烦。为了解决这类问题,构造双链表,就是在单链表的基础上,多加一个指针域,指向当前节点的前驱,这样方便的从后继找到前驱。同样,双链表也分为带头结点和不带头结点的双链表,情况类似于单链表。带头结点的双链表,当head->next为NULL时链表为空;不带头结点的双链表,当head为NULL时,链表为空。
  3. 循环单链表:只要将单链表的最后一个指针域指向链表的第一个结点,就可以形成循环单链表。循环单链表可以实现从任意一个结点访问链表中任何结点。带头结点的循环单链表,当head等于head->next时,链表为空;不带头结点的循环单链表,当head等于NULL时,链表为空。
  4. 循环双链表:将终端结点的next指针指向链表中的第一个结点,将链表中第一个结点的prior指针指向终端结点。循环双链表同样有带结点和不带头结点之分,当head等于NULL时,不带头结点的循环双链表为空。带头结点的循环链表是没有空指针,其空状态,head->next和head->prior必然都是等于head,所以判断判断其空,只要检查head->next或head->prior两个指针的任意一个是否等于head即可。
  5. 静态链表:用一个二维数组描述。数组的下标表示地址,一个维表示数据,另一个维表示指针,指向上一个元素的下标,如果是终端结点则指针维度表示为-1。

常见问题

  1. 基于空间的比较
    1. 存储分配的方式:顺序表的存储空间一次性分配的,链表的存储空间是多次分配的。
    2. 存储密度(存储密度=结点值域所占的存储量/结点所占的存储总量):顺序表的存储密度为1,链表的存储密度小于1(因为有指针域)。
  2. 基于时间的比较
    1. 存取方式:顺序表可以随机存取,也可以顺序存取。链表只能顺序存取。
    2. 插入/删除时移动元素的个数:顺序表平均需要移动近一半元素;链表不需要移动元素,只需要修改指针即可。

线性表的结构体定义和基本操作

线性表的结构体定义

#define maxSize 100 //定义一个整数常量maxSize,值为100
  1. 顺序表的结构体定义
typedef struct Sqlist{
    int data[maxSize];
    int length;
}Sqlist;
  1. 单链表结点定义
//设置的是带头结点的单链表
typedef struct LNode{
    int data; //data中存放数据域
    struct LNode *next; //指向后继结点的指针
}LNode;//定义单链表结点类型
  1. 双链表结点定义
typedef struct DLNode{
    int data;
    struct DLNode *prior; //指向前驱结点的指针
    struct DLNode *next; //指向后继节点的指针
}DLNode;

结点是内存中一片由用户分配的存储空间,只有一个地址来表示它的存在,没有显式的名称,因此会在分配链表结点空间的时候,同时定义一个指针,来存储这片空间的地址。

例如:LNode *A = (LNode*)malloc(sizeof(LNode));,用户分配了一片LNode型的结点,也就是构造了一个LNode型的结点。注意这里A命名了2个东西:一个是结点,另一个是指向这个结点的指针。

顺序表的操作

操作定义

//初始化顺序表
Sqlist* initList();
//向数组后插入数据元素
int insertElem(Sqlist *L,int e);
//将e元素插入到位置p上
int insertPosElem(Sqlist *sqlist,int e,int p);
//按元素查找下标
int findElem(Sqlist sqlist,int e);
//删除下标为p的元素
int deleteElem(Sqlist *sqlist,int p,int *e);
//求指定位置元素
int getElem(Sqlist sqlist,int p,int *e);
//返回第一个比x大的元素的位置
int findFirstElem(Sqlist sqlist,int x);

操作实现

Sqlist* initList(){
    Sqlist *sqlist = (Sqlist*) malloc(sizeof(Sqlist)); //创建该结构体即创建出数组。
    sqlist->length = 0;
    return sqlist;
}

int insertElem(Sqlist *L,int e){
    if(L->length == maxSize){
        return 0;
    }
    L->data[L->length] = e;
    L->length++;
    return 1;
}

int insertPosElem(Sqlist *sqlist,int e,int p){
    int i;
    if(p < 0 || p > sqlist->length || sqlist->length == maxSize){
        return 0;
    }
    for(i = sqlist->length-1 ; i>=p ; --i){
        sqlist->data[i+1] = sqlist->data[i];
    }
    sqlist->data[p] = e;
    ++sqlist->length;
    return 1;
}

int findElem(Sqlist sqlist,int e){
    for (int i = 0; i < sqlist.length; ++i) {
        if(e == sqlist.data[i]){
            return i;
        }
        return -1;
    }
}

int deleteElem(Sqlist *sqlist,int p,int *e){
    if(p<0 || p>sqlist->length-1){
        return 0;
    }
    *e = sqlist->data[p];
    for (int i = p; i < sqlist->length - 1; ++i) {
        sqlist->data[i] = sqlist->data[i+1];
    }
    --(sqlist->length);
    return 1;
}

int getElem(Sqlist sqlist,int p,int *e){
    if(p<0 || p>sqlist.length-1){
        return 0;
    }
    *e = sqlist.data[p];
    return 1;
}

int findFirstElem(Sqlist sqlist,int x){
    int i;
    for (i = 0; i < sqlist.length; ++i) {
        if(x < sqlist.data[i]){
            return i;
        }
    }
    return -1;
}

单链表的操作

操作定义

//尾插法建立单链表
LNode* createListR(int a[],int n);
//头插法建立单链表
LNode* createListF(int a[],int n);
//遍历打印链表
void printList(LNode* list);
//尾插法插入元素
void insertListR(LNode* list,int data);
//头插法插入元素
void insertListF(LNode* list,int data);
//将两个递增的单链表归并为一个递增的单链表
LNode* mergeUp(LNode *listA,LNode *listB);
//将两个递增的单链表归并为一个递减的单链表
LNode* mergeDe(LNode* listA,LNode* listB);
//按值查找并删除该节点
int findAndDelete(LNode* list,int x);

操作实现

LNode* createListR(int a[],int n){
    LNode* list = (LNode*) malloc(sizeof(LNode));
    list->next = nullptr;
    LNode* tmpList = list;
    for (int i = 0; i < n; ++i) {
        LNode* newNode = (LNode*) malloc(sizeof(LNode));
        newNode->next = nullptr;
        newNode->data = a[i];
        tmpList->next = newNode;
        tmpList = tmpList->next;
    }
    return list;
}

LNode* createListF(int a[],int n){
    LNode* list = (LNode*) malloc(sizeof(LNode));
    list->next = nullptr;
    LNode* tmpList = list;
    for (int i = 0; i < n; ++i) {
        LNode* newNode = (LNode*) malloc(sizeof(LNode));
        newNode->data = a[i];
        newNode->next = nullptr;
        //头插法的关键步骤
        newNode->next = tmpList->next; //newNode的next指向list头结点的next。
        tmpList->next = newNode; //list头结点的next指向newNode。
    }
    return list;
}

void insertListR(LNode* list,int data){
    LNode* tempList = list;
    LNode* newNode = (LNode*)malloc(sizeof(LNode));
    newNode->data = data;
    newNode->next = nullptr;
    while(tempList!=nullptr){
        tempList = tempList->next;
    }
    tempList->next = newNode;
}

LNode* mergeUp(LNode *listA,LNode *listB){
    LNode *p = listA->next;
    LNode *q = listB->next;
    LNode *listC = (LNode*)malloc(sizeof(LNode));
    LNode *tempListC = listC;
    while(q!=nullptr && p!=nullptr){
        if(p->data <= q->data){
            LNode* newNode = (LNode*)malloc(sizeof(LNode));
            newNode->data = p->data;
            newNode->next = nullptr;
            tempListC->next = newNode;
            tempListC = tempListC->next;
            p = p->next;
        }else{
            LNode* newNode = (LNode*)malloc(sizeof(LNode));
            newNode->data = q->data;
            newNode->next = nullptr;
            tempListC->next = newNode;
            tempListC = tempListC->next;
            q = q->next;
        }
    }
    if(p!=nullptr){ //因为p后面的元素不变,所以仍然连接,只需要把p连到C后。
        tempListC->next = p;
    }
    if(q!=nullptr){
        tempListC->next = q;
    }
    return listC;
}

LNode* mergeDe(LNode* listA,LNode* listB){
    LNode* p = listA->next;
    LNode* q = listB->next;
    LNode *listC = (LNode*) malloc(sizeof(LNode));
    listC->next = nullptr;
    LNode *tempListC = listC;
    while(p!=nullptr && q!=nullptr){
        if(p->data <= q->data){
            insertListF(listC,p->data);
            p = p->next;
        }else{
            insertListF(listC,q->data);
            q = q->next;
        }
    }
    while(p != nullptr){
        insertListF(listC,p->data);
        p = p->next;
    }
    while(q != nullptr){
        insertListF(listC,q->data);
        q = q->next;
    }
    return listC;
}

void insertListF(LNode* list,int data){
    LNode* newNode = (LNode*) malloc(sizeof(LNode));
    newNode->next = nullptr;
    newNode->data = data;
    LNode *tempList = list;
    newNode->next = tempList->next;
    tempList->next = newNode;
}

int findAndDelete(LNode* list,int x){
    LNode *p,*q;
    p = list;
    while(p->next != nullptr){
        if(p->next->data == x){
            break;
        }
        p = p->next;
    }
    if(p->next == nullptr){
        return 0;
    }else{
        q = p -> next;
        p->next = p->next->next;
        free(q);
        return 1;
    }
}

void printList(LNode* list){
    LNode* tempNode = list->next;
    while (tempNode != nullptr){
        printf("%d ",tempNode->data);
        tempNode = tempNode->next;
    }
}

双链表的操作

操作定义

//尾插法创建双向链表
DLNode* createDListR(int a[],int n);
//遍历打印链表
void printDList(DLNode* head);
//尾插法插入元素
void insertListR(DLNode* head,int element);
//头插法插入元素
void insertListL(DLNode* head,int element);
//删除element元素
void deleteList(DLNode* head,int element);

操作实现

DLNode* createDListR(int a[],int n){
    DLNode* head = (DLNode*)malloc(sizeof(DLNode));
    head->next = nullptr;
    head->prior = nullptr;
    DLNode* tempHead = head;
    for (int i = 0; i < n; ++i) {
        DLNode *newNode = (DLNode*)malloc(sizeof(DLNode));
        newNode->data = a[i];
        newNode->next = nullptr;
        tempHead->next = newNode;
        newNode->prior = tempHead;
        tempHead = tempHead->next;
    }
    return head;
}

void insertListR(DLNode* head,int element){
    DLNode *temp = head->next;
    while(temp->next != nullptr){
        temp = temp->next;
    }
    DLNode *newNode = (DLNode*)malloc(sizeof(DLNode));
    newNode->data = element;
    newNode->next = nullptr;
    temp->next = newNode;
    newNode->prior = temp;
}

void insertListL(DLNode* head,int element){
    DLNode *newNode = (DLNode*)malloc(sizeof(DLNode));
    newNode->data = element;
    newNode->next = nullptr;
    newNode->prior = nullptr;
    DLNode *temp = head;
    DLNode *tempNext = head->next;
    newNode->next = tempNext;
    head->next = newNode;
    newNode->prior = head;
    tempNext->prior = newNode;
}

void deleteList(DLNode* head,int element){
    DLNode *temp = head;
    while(temp != nullptr){
        if(temp->data == element){
            break;
        }
        temp = temp->next;
    }
    temp = temp->prior;
    temp->next = temp->next->next;
    temp->next->prior = temp;
}

void printDList(DLNode* head){
    DLNode *temp = head->next;
    while (temp != nullptr){
        printf("%d ",temp->data);
        temp = temp->next;
    }
    printf("\n");
}

循环链表的操作

循环单链表和循环双链表都是由对应的单链表和双链表改造而来的,只需要在终端结点和头结点建立联系即可。循环单链表终端结点的next指向表头结点;循环双链表终端结点的next指向表头结点,头结点的prior指针指向表尾结点。需要注意的是,如果p指针沿着循环链表走下去,则p走到表尾的条件为p->next==head。操作与单链表和双链表相同。

逆置问题

给定一个线性表,如何将其中的元素逆置?可设置两个整型变量i和j,i指向第一个元素,j指向最后一个元素,边交换i和j元素,边让i和j相向而行,直到相遇。实现如下,假设元素存于a[],left和right是数组两端的下标。

for(int i = left,j = right;i < j; i++,j--){
	temp = a[i];
	a[i] = a[j];
	a[j] = temp;
}

逆置问题:给定一个线性表,将其中的元素逆置。

  1. 将一长度为n的数组的前端k个元素逆序后移动到数组后端,要求原数组中数据不丢失,其余元素的位置无关紧要。
    • 只需要逆置整个数组,即满足前端k个元素逆序后放到数组的后端。
  2. 将一长度为n的数组的前端k个元素保持原序移动到数组后端,要求原数组中数据不丢失,其余的位置无关紧要。
    • 只需要将前端k个元素逆置,然后将整个数组逆置。
  3. 将数组的元素(x0,x1,x2,…,xn-1)经过移动变成(xp,xp+1,…,xn-1.x0,x1,…,xp-1),即循环左移p个单位。
    • 只需将0到p-1位置的元素逆置,再将p~n-1逆置,然后将整个元素逆置。
//将一长度为n的数组的前端k个元素逆序后移动到数组后端,要求原数组中数据不丢失,其余元素的位置无关紧要。
void reverse(int a[],int left,int right,int k){
    int temp;
    for (int i = left,j = right; i < left+k && i < j; ++i,--j) {
        temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
}

//将一长度为n的数组的前端k个元素保持原序移动到数组后端,要求原数组中数据不丢失,其余的位置无关紧要。
void moveToEnd(int a[],int n,int k){
    reverse(a,0,k-1,k);
    reverse(a,0,n-1,k);
}

//将数组的元素(x0,x1,x2,...,xn-1)经过移动变成(xp,xp+1,...,xn-1.x0,x1,...,xp-1),即循环左移p个单位.
void moveP(int a[],int n,int p){
    reverse(a,0,p-1,p);
    reverse(a,p,n-1,n-p);
    reverse(a,0,n-1,n);
}

//输出数组
void printArray(int a[],int length){
    for (int i = 0; i < length; ++i) {
        printf("%d ",a[i]);
    }
    printf("\n");
}

分享:

低价透明

统一报价,无隐形消费

金牌服务

一对一专属顾问7*24小时金牌服务

信息保密

个人信息安全有保障

售后无忧

服务出问题客服经理全程跟进