文章目錄

線性表的基本概念
- <1>定義
- <2>性質
線性表的順序存儲結構
- 1.基本概念
- 2.設計與實作
- 3.優點和缺點

線性表的基本概念

<1>定義

線性表是0個或者多個資料元素的集合

線性表中的資料元素之間是有序的

線性表中的資料元素個數是有限的

線性表中的資料元素類型必須相同

<2>性質

a0為線性表的第一個元素，隻有一個後繼

an為線性表的最後一個元素，隻有一個前驅

除這二者外的其他元素ai，既有前驅，又有後繼

線性表能夠逐項和順序存取

線性表的順序存儲結構

1.基本概念

線性表的順序存儲結構，指的是用一段位址連續的存儲單元依次存儲線性表的資料元素

C語言資料結構——線性表的順序存儲結構線性表的基本概念線性表的順序存儲結構

2.設計與實作

在寫程式之前，先說明一下單連結清單的頭插法和尾插法

頭插法：從一個空表開始，重複讀入資料，生成新的結點，将讀入的資料存放到新的結點的資料域中，然後将新結點插入到目前連結清單的表頭結點之後。

尾插法：從一個空表開始，重複讀入資料，生成新的結點，将讀入的資料存放到新的結點的資料域中，然後将新結點插入到目前連結清單的表尾結點之後。

首先先創造一個整體的架構，先自定一個header檔案，然後把想要實作的方法寫入，然後直接在主程式中導入此頭檔案

header.h

#ifndef CPRIMERPLUS_HEADER_H
#define CPRIMERPLUS_HEADER_H
typedef void SeqList;//聲明一下線性表
typedef void SeqListNode;//聲明組成結點的結構體

SeqList *seqList_Create(int capacity);//建立一張線性表

void SeqList_Destroy(SeqList *list);//銷毀一張線性表

void SeqList_Clear(SeqList *list);//清空結點元素

int SeqList_Length(SeqList *list);//傳回線性表的長度

int SeqList_Insert(SeqList *list,SeqListNode *node,int pos);//向SeqList連結清單pos的位置插入一個結點node

SeqListNode *list_Get(SeqList *list , int pos);//擷取pos位置元素

SeqListNode *list_Delete(SeqList *list,int pos);//删除pos位置元素

#endif //CPRIMERPLUS_HEADER_H

頭檔案總體的思路寫好後，下面再把主程式中的使用寫出來

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "header.h"
typedef struct Teacher{
    int age;
    char *name;
}Teacher;
int main(){
    int ret = 0;
    SeqList *list = NULL;
    Teacher t1,t2,t3,t4,t5;
    t1.age = 30;
    t2.age = 31;
    t3.age = 32;
    t4.age = 33;
    t5.age = 34;

    list = seqList_Create(10);
    ret = SeqList_Insert(list, (SeqListNode *) &t1, 0);//頭插法
    ret = SeqList_Insert(list, (SeqListNode *) &t2, 0);
    ret = SeqList_Insert(list, (SeqListNode *) &t3, 0);
    ret = SeqList_Insert(list, (SeqListNode *) &t4, 0);
    ret = SeqList_Insert(list, (SeqListNode *) &t5, 0);

    //周遊單連結清單，擷取結點
    for (int i = 0; i < SeqList_Length(list); ++i) {
        Teacher *t = (Teacher *) list_Get(list, i);
        if (t == NULL) {
            return 0;
        }
        printf("t->age:%d", t->age);
    }

    //删除連結清單中的結點
    for (int j = 0; j < SeqList_Length(list); ++j) {
        list_Delete(list, 0);
    }
    system("pause");
}

然後最後再把細節寫好，主要采用的還是頭插法插入。

在同一個directory下建立具體方法的實作即可。

思路：

1.先把連結清單的結構寫好，可以用struct，也可以用typedef struct起别名

typedef struct SeqList{
    int length;//連結清單實際長度
    int capacity;//配置設定最大的容量
    unsigned int *node;//所有的結點所形成的數組
    // (動态庫内的結點，有多少配置設定多少，是動态的,是以要用指針指向記憶體空間内的結點)
}tSeqList;

2.在連結清單的create方法中，先讓連結清單初始空間為Nul，然後為其動态配置設定存儲空間，因為我們是動态連結清單，然後配置設定的類型和node的類型一緻即可，配置設定完連結清單的空間後，為配置設定好的空間引入memset方法

void *memset(void *s,int c,size_t n)

總的作用：将已開辟記憶體空間s的首n個位元組的值設為值c。

然後根據capacity配置設定node的空間，方法都是一樣的

最後去給容量和結點賦初值，第一個函數也就寫完了

SeqList *seqList_Create(int capacity){
    tSeqList *tmp = NULL;//既可以在棧配置設定記憶體空間，也可以在堆配置設定記憶體空間，但是讓初始的連結清單為空
    tmp = (tSeqList *) malloc(sizeof(tSeqList));
    if(tmp ==NULL) {
        printf("func SeqList_Create error:%d",0);
        return NULL;
    }

    memset(tmp, 0, sizeof(tSeqList));//總的作用：将已開辟記憶體空間tmp的首sizeof(tSeqList)個位元組的值設為值0


//    根據capacity配置設定結點空間
    tmp->node = (unsigned int *) malloc(sizeof(unsigned int *) * capacity);
    if (tmp->node == NULL) {
        printf("func SeqList_Create error:%d",0);
        return NULL;
    }
    tmp->capacity = capacity;
    tmp->length = 0;
    return tmp;

}

3.下面我們開始寫destroy函數，因為我們之前開辟了兩次記憶體空間(seqlist和node)，是以也應該是先釋放後開辟的空間

void SeqList_Destroy(SeqList *list){
    tSeqList *tList = NULL;
    if (list == NULL) {
        return;
    }
    tList = (tSeqList *) list;
    if (tList->node != NULL) {
        free(tList->node);
    }
    free(tList);
}

4.然後寫clear清空連結清單函數，但是不是銷毀free掉，而是讓連結清單長度回歸為0

//清空連結清單
void SeqList_Clear(SeqList *list){
    tSeqList *tList = NULL;
    if (list == NULL) {
        return;
    }
    tList = (tSeqList *) list;
    tList->length = 0;
}

5.然後求取連結清單長度

//求連結清單長度
int SeqList_Length(SeqList *list){
    tSeqList *tList = NULL;
    if (list == NULL) {
        return 0;
    }
    tList = (tSeqList *) list;
    return tList->length;
}

6.然後寫元素插入。

思路：

1.判斷線性表是否合法

2.判斷插入位置是否合法

3.把最後一個元素插入進去之後，要把後面的往後挪動一個機關

4.将新元素插入

5.線性表長度+1

元素插入分為兩個階段，第一個階段是元素的後移，第二個階段是給空出的位置進行指派

元素後移：一般的情況下都好說，要是後移之後超過capacity，要判斷length==capacity？或者甚至超過，如果超過立刻return一個提示消息，這是第一種元素後移的bug。第二種元素後移的bug就是，pos的位置，也就是插入位置比length還大，那我們就要進行容錯修正，這時就比較自由了，可以重新定義，或者寫一個容錯修正的算法。

int SeqList_Insert(SeqList *list,SeqListNode *node,int pos){
    int ret = 0;
    tSeqList *tList = NULL;
    if (list == NULL || node == NULL || pos < 0) {
        return ret;
    }
    tList = (tSeqList *) list;
    //判斷插入元素是否滿了
    if (tList->length == tList->capacity) {
        printf("滿了");
    }
//    容錯修正，pos>length
    if (pos > tList->length) {
        pos = tList->length;
    }
    //1.元素後移
    int i = 0;
    for (i = (*tList).length; i > pos; --i) {
        tList->node[i] = (*tList).node[i - 1];
    }
    //2.插入元素
    tList->node[i] = (unsigned int) node;
    tList->length++;
}

7.擷取元素，擷取元素就比插入元素稍微好寫一點，要是也要對插入位置pos進行判斷。

SeqListNode *list_Get(SeqList *list , int pos){
    int i = 0, ret = 0;
    tSeqList *tList = NULL;
    if (list == NULL || pos < 0) {
        ret = -1;
        return ret;
    }
    tList = (tSeqList *) list;
    return tList->node[pos];
}

8.删除元素

假設我們删除掉第n個結點，首先我們要把這個結點的位置緩存出來，然後把後面的結點依次指派過來。

SeqListNode *list_Delete(SeqList *list,int pos){
    SeqListNode *ret = 0;
    tSeqList *tList = NULL;
    if (list == NULL || pos < 0) {
        printf("産生了錯誤");
        return NULL;
    }
    tList = (tSeqList *) list;
    ret = (SeqListNode *) tList->node[pos];
    for (int i = pos+1; i <tList->length; ++i) {
        tList->node[i - 1] = tList->node[i];
    }
    tList->length--;
    return ret;
}

3.優點和缺點

優點：無需為線性表中的邏輯關系增加額外的空間，可以快速的擷取表中合法位置的元素

缺點：插入和删除需要移動大量的結點，當線性表長度較大的時候難以确定存儲空間的容量

C語言資料結構——線性表的順序存儲結構線性表的基本概念線性表的順序存儲結構

文章目錄

線性表的基本概念

<1>定義

<2>性質

線性表的順序存儲結構

1.基本概念

2.設計與實作

3.優點和缺點

繼續閱讀

goalng nil interface淺析持續學習

模組化：數學模組化

開源軟體：NoSql資料庫 - 圖資料庫 Neo4j轉載自原文位址：http://www.cnblogs.com/loveis715/p/5277051.html

資料在網絡7層中的傳輸過程

當今世界十大經典算法

字元串功能實作

【算法提高班】貪婪政策

《貪婪的動态規劃》

分治法實作求解最大子數組

UVA 10154:Weights and Measures Weights and Measures

Linux Kernel Development　學習

動态規劃、最小費用流例題 — nyoj_712 探尋寶藏

計算機開路人阿蘭·圖靈

基礎算法之二分查找

poj3249

PAT 1089 Insert or Merge[難]