第一课
线性表的深度理解
- 以下哪个选项对线性表的描述是正确的？
a. 班级中同学的友谊关系
b. 公司中的上下级关系
c. 冬天图书排队占座关系
d. 花名册上名字之间的关系 - 正确答案是（d）
线性表的定义
- 线性表是零个或多个数据元素的集合
- 线性表中的数据元素之间是有顺序的
- 线性表中的数据元素个数是有限的
- 线性表中的数据元素的类型必须相同
线性表的性质
- a0为线性表的第一个元素，只有一个后继
- an为线性表的最后一个元素，只有一个前驱
- 除a0和an外的其他元素ai，既有前驱，又有后继
- 线性表能够逐项访问和顺序存取
小结
- 线性表是数据元素的有序并且有限的集合
- 线性表中的数据元素必须是类型相同的
- 线性表可用于描述“队列类型”关系的问题
第二课
线性表的一些常用操作
- 创建线性表
- 销毁线性表
- 清空线性表
- 将元素插入线性表
- 将元素从线性表中删除
- 获取线性表中某个位置的元素
- 获取线性表的长度
线性表操作的实现
- 线性表在程序中表现为一种特殊的数据类型
- 线性表的操作在程序中的表现为一组函数
小结
- 线性表在程序中表现为一种特殊的数据类型
- 线性表的操作则表现为一组相关的函数
第三课
顺序存储的定义
线性表的顺序存储结构，指的是用一段地址连续的存储单元依次存储线性表的数据元素
用一维数组来实现顺序存储结构
- 存储空间的起始位置：数组node
- 线性表的最大容量：数组长度MAXSIZE
- 线性表的当前长度：length
获取元素操作
- 判断线性表是否合法
- 判断位置是否合法
- 直接通过数组下标的方式获取元素
插入元素操作
- 判断线性表是否合法
- 判断插入位置是否合法
- 把最后一个元素到插入位置的元素后移一个位置
- 将新元素插入
- 线性表长度加一
删除元素操作
- 判断线性表是否合法
- 判断删除位置是否合法
- 将元素取出
- 将删除位置后的元素分别向前移动一个位置
- 线性表长度减一
创建可复用的顺序线性表（附代码）
优点
- 无需为线性表中的逻辑关系增加额外的空间
- 可以快速的获取表中合法位置的元素
缺点
- 插入和删除操作需要移动大量元素
- 当线性表长度变化较大时难以确定存储空间的容量
代码
List.h
#ifndef _LIST_H_
#define _LIST_H_
typedef void List;
typedef void ListNode;
/*
该方法用于创建并且返回一个空的线性表
*/
List* List_Create(int capacity);
/*
该方法用于销毁一个线性表list
*/
void List_Destroy(List* list);
/*
该方法用于将一个线性表list中的所有元素清空
使得线性表回到创建时的初始状态
*/
void List_Clear(List* list);
/*
该方法用于返回一个线性表list中的所有元素个数
*/
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);
}
