第一課

線性表的深度理解

• 以下哪個選項對線性表的描述是正確的？
  a. 班級中同學(xué)的友誼關(guān)系
  b. 公司中的上下級關(guān)系
  c. 冬天圖書排隊占座關(guān)系
  d. 花名冊上名字之間的關(guān)系
• 正確答案是（d）

線性表的定義

• 線性表是零個或多個數(shù)據(jù)元素的集合
• 線性表中的數(shù)據(jù)元素之間是有順序的
• 線性表中的數(shù)據(jù)元素個數(shù)是有限的
• 線性表中的數(shù)據(jù)元素的類型必須相同

線性表的性質(zhì)

• a0為線性表的第一個元素，只有一個后繼
• an為線性表的最后一個元素，只有一個前驅(qū)
• 除a0和an外的其他元素ai，既有前驅(qū)，又有后繼
• 線性表能夠逐項訪問和順序存取

小結(jié)

• 線性表是數(shù)據(jù)元素的有序并且有限的集合
• 線性表中的數(shù)據(jù)元素必須是類型相同的
• 線性表可用于描述“隊列類型”關(guān)系的問題

第二課

線性表的一些常用操作

• 創(chuàng)建線性表
• 銷毀線性表
• 清空線性表
• 將元素插入線性表
• 將元素從線性表中刪除
• 獲取線性表中某個位置的元素
• 獲取線性表的長度

線性表操作的實現(xiàn)

• 線性表在程序中表現(xiàn)為一種特殊的數(shù)據(jù)類型
• 線性表的操作在程序中的表現(xiàn)為一組函數(shù)

小結(jié)

• 線性表在程序中表現(xiàn)為一種特殊的數(shù)據(jù)類型
• 線性表的操作則表現(xiàn)為一組相關(guān)的函數(shù)

第三課

順序存儲的定義

線性表的順序存儲結(jié)構(gòu)，指的是用一段地址連續(xù)的存儲單元依次存儲線性表的數(shù)據(jù)元素

用一維數(shù)組來實現(xiàn)順序存儲結(jié)構(gòu)

• 存儲空間的起始位置：數(shù)組node
• 線性表的最大容量：數(shù)組長度MAXSIZE
• 線性表的當前長度：length

獲取元素操作

• 判斷線性表是否合法
• 判斷位置是否合法
• 直接通過數(shù)組下標的方式獲取元素

插入元素操作

• 判斷線性表是否合法
• 判斷插入位置是否合法
• 把最后一個元素到插入位置的元素后移一個位置
• 將新元素插入
• 線性表長度加一

刪除元素操作

• 判斷線性表是否合法
• 判斷刪除位置是否合法
• 將元素取出
• 將刪除位置后的元素分別向前移動一個位置
• 線性表長度減一

創(chuàng)建可復(fù)用的順序線性表（附代碼）

優(yōu)點

• 無需為線性表中的邏輯關(guān)系增加額外的空間
• 可以快速的獲取表中合法位置的元素

缺點

• 插入和刪除操作需要移動大量元素
• 當線性表長度變化較大時難以確定存儲空間的容量

代碼

List.h

#ifndef _LIST_H_
#define _LIST_H_

typedef void List;
typedef void ListNode;

/*
    該方法用于創(chuàng)建并且返回一個空的線性表
*/
List* List_Create(int capacity);

/*
    該方法用于銷毀一個線性表list
*/
void List_Destroy(List* list);

/*
    該方法用于將一個線性表list中的所有元素清空
    使得線性表回到創(chuàng)建時的初始狀態(tài)
*/
void List_Clear(List* list);

/*
    該方法用于返回一個線性表list中的所有元素個數(shù)
*/
int List_Length(List* list);

/*
    該方法用于向一個線性表list的pos位置處插入新元素node
    返回值為1表示插入成功，0表示插入失敗
*/
int List_Insert(List* list, ListNode* node, int pos);

/*
    該方法用于獲取一個線性表list的pos位置處的元素
    返回值為pos位置處的元素，NULL表示獲取失敗
*/
ListNode* List_Get(List* list, int pos);

/*
    該方法用于刪除一個線性表list的pos位置處的元素
    返回值為被刪除的元素，NULL表示刪除失敗
*/
ListNode* List_Delete(List* list, int pos);

#endif

List.c

#include <stdio.h>
#include <malloc.h>
#include "List.h"

typedef unsigned int TListNode;
typedef struct _tag_List
{
    int capacity;
    int length;
    TListNode* node;
}TList;

List* List_Create(int capacity){
    TList* ret = NULL;
    if(capacity >= 0)
    {
        ret = (TList*)malloc(sizeof(TList)+sizeof(TListNode)*capacity);
    }
    if(ret != NULL)
    {
        ret->capacity = capacity;
        ret->length = 0;
        ret->node = (TListNode*)(ret+1);
    }
    return ret;
}

void List_Destroy(List* list){
    free(list);
}

void List_Clear(List* list){
    TList* slist = (TList*)list;
    if(slist != NULL)
    {
        slist->length = 0;
    }
} 

int List_Length(List* list){
    TList* slist = (TList*)list;
    int ret = -1;
    if(slist != NULL)
    {
        ret = slist->length;
    }
    return ret;
}

int List_Insert(List* list, ListNode* node, int pos){
    TList* slist = (TList*)list;
    int ret = (slist != NULL);
    int i = 0;
    ret = ret && (slist->length + 1 <= slist->capacity);
    ret = ret && (0 <= pos);
    if(ret)
    {
        if(pos >= slist->length)
        {
            pos = slist->length;
        }
        for(i=slist->length;i>pos;i--)
        {
            slist->node[i] = slist->node[i-1];
        }
        slist->node[i] = (TListNode*)node;
        slist->length++;
    }
    return ret;
}

ListNode* List_Get(List* list, int pos){
    TList* slist = (TList*)list;
    ListNode* ret = NULL;
    if((slist != NULL) && (0 <= pos) && (pos <= slist->length))
    {
        ret = (ListNode*)slist->node[pos];
    }
    return ret;
}

ListNode* List_Delete(List* list, int pos){
    ListNode* ret = List_Get(list,pos);
    TList* slist = (TList*)list;
    int i = 0;
    if(ret != NULL)
    {
        for(i=pos+1;i<slist->length;i++)
        {
            slist->node[i-1] = slist->node[i];
        }
        slist->length--;
    }
    return ret;
}

main.c

#include <stdio.h>
#include <stdlib.h>
#include "List.h"
int main(int argc, char *argv[])
{
    List* list = List_Create(5);
    int i=0;
    int j=1;
    int k=2;
    int x=3;
    int y=4;
    int z=5;
    int index=0;
    List_Insert(list,&i,0);
    List_Insert(list,&j,0);
    List_Insert(list,&k,0);
    List_Insert(list,&x,0);
    List_Insert(list,&y,0);
    List_Insert(list,&z,0);
    for(index=0;index<List_Length(list);index++)
    {
        int* p = (int*)List_Get(list,index);
        printf("%d\n",*p);
    }
    printf("\n");
    while(List_Length(list)>0)
    {
        int* p = (int*)List_Delete(list,0);
        printf("%d\n",*p);
    }
    List_Destroy(list);
}