1. 線性表：n個數據元素的有序集合。
線性表是一種常用的數據結構。在實際應用中，線性表都是以棧、隊列、字符串、數組等特殊線性表的形式來使用的。由于這些特殊線性表都具有各自的特性，因此，掌握這些特殊線性表的特性，對于數據運算的可靠性和提高操作效率都是至關重要的。 線性表是一個線性結構，它是一個含有n≥0個結點的有限序列，對于其中的結點，有且僅有一個開始結點沒有前驅但有一個后繼結點，有且僅有一個終端結點沒有后繼但有一個前驅結點，其它的結點都有且僅有一個前驅和一個后繼結點。
特征：
1．集合中必存在唯一的一個“第一元素”；
2．集合中必存在唯一的一個 “最后元素” ；
3．除最后一個元素之外，均有 唯一的后繼(后件)；
4．除第一個元素之外，均有 唯一的前驅(前件)。
java中的List接口，就是線性表。ArrayList就是順序線性表，LinkedList就是鏈表線性表。
2. 線性表的順序表示：ArrayList
一般使用數組(C語言中的數組采用順序存儲方式。即連續地址存儲)來描述。
優點：在于隨機訪問元素，
缺點：插入和和刪除的時候，需要移動大量的元素。
c語言實現代碼：
// Test.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include <stdio.h>
#include "stdlib.h"
//宏定義
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
#define LT(a,b) ((a)<(b))
#define N = 100
#define LIST_INIT_SIZE 100 //線性表初始空間分配量
#define LISTINCREMENT 10 //線性表空間分配的增量
typedef int Status;
typedef int ElemType;
typedef struct LNode{
ElemType *elem; //存儲空間的基地址
int lenght; //當前的長度
int listsize; //當前分配的存儲容量
}SqList;
/**
*構造空的線性表
*/
Status initList(SqList &L, int lenght){
if (lenght == 0) lenght = LIST_INIT_SIZE;
L.elem = (ElemType *)malloc(lenght * sizeof(ElemType));
if(!L.elem) exit(OVERFLOW); //分配存儲空間失敗
L.lenght = 0; //初始空表長度為0
L.listsize = lenght ;//初始存儲容量為100
return OK;
}
/************************************************************************/
/* 在第i位置插入e
*/
/************************************************************************/
Status insertList(SqList &L, ElemType e, int i){
ElemType *p, *q;
if(i<0 ||i > L.lenght) return ERROR; //i值不合法
if (L.lenght >= L.listsize) {
ElemType *newbase = (ElemType *)realloc(L.elem ,(L.listsize +LISTINCREMENT)*sizeof(ElemType));
if(!newbase) return OVERFLOW; //存儲分配失敗
L.elem = newbase; //新基值
L.listsize += LISTINCREMENT; //增加存儲容量
}
q = &L.elem[i]; //q為插入的位置
for (p = &L.elem[L.lenght]; p>=q; --p) {
*p = *(p-1); //i元素之后的元素往后移動
}
*q = e; //插入e
L.lenght +=1;
return OK;
}
/************************************************************************/
/* 快速排序
*/
/************************************************************************/
void sortList(SqList &L){
}
/************************************************************************/
/* 刪除第i位置元素，并用e返回其值 */
/************************************************************************/
Status deleteListElem(SqList &L, int i, ElemType &e){
int *p, *q;
if(i<0 ||i > L.lenght) return ERROR; //i值不合法
q = &L.elem[i]; //被刪除元素的位置為i，L.elem就是數組名,
e = *q; //被刪除元素的值賦值給e
for (p = q; p< (L.elem + L.lenght); p++){ //元素左移
*p = *(p+1);
}
--L.lenght;
return OK;
}
/************************************************************************/
/* 快速排序
*/
/************************************************************************/
int partition(SqList &L, ElemType low, ElemType high){
ElemType pivotkey = L.elem[low]; //樞軸記錄關鍵字
while (low < high) { //從表的兩端向中間掃描
while (low < high && L.elem[high] >= pivotkey ) --high;//高端位置掃描
L.elem[low] = L.elem[high]; //交換數據，小于pivotkey移到低端
L.elem[high] = pivotkey;
while (low < high && L.elem[low] <= pivotkey ) ++low; //低端掃描
L.elem[high] = L.elem[low]; //交換數據 大于pivotkey移到高端
L.elem[low] = pivotkey;
}
return low;
}
void quickSort(SqList &L, ElemType low, ElemType high){
int pivot;
if(low < high) {
pivot = partition(L, low, high);
quickSort(L, low, pivot -1); //低端子表排序
quickSort(L, pivot +1, high); //高端子表排序
}
}
/************************************************************************/
/*
合并兩個線性表
*/
/************************************************************************/
void mergeList(SqList La, SqList Lb, SqList &Lc){
ElemType *pa, *pb, *pc;
Lc.listsize = La.lenght + Lb.lenght;
initList(Lc, Lc.listsize); //初始化LC\pc = Lc.elem;
Lc.lenght = Lc.listsize;
pc = Lc.elem;
pa = La.elem;
pb = Lb.elem;
while (pa <= &La.elem[La.lenght -1] && pb <= &Lb.elem[Lb.lenght -1]){
if (*pa <= *pb) *pc++ = *pa++;
else *pc++ = *pb++;
}
while(pa <= &La.elem[La.lenght -1]) *pc++ = *pa++; //插入La的剩余元素
while(pb <= &Lb.elem[Lb.lenght -1]) *pc++ = *pb++; //插入Lb的剩余元素
}
/************************************************************************/
/* 打印list
*/
/************************************************************************/
void printList(SqList L){
printf("當前值:");
for (int i =0; i<L.lenght;i++) {
printf("%d ", *(L.elem+i)); // L.elem為首地址
}
printf("\r\n");
}
void main()
{
SqList La,Lb,Lc;
ElemType e;
int init,i;
init = initList(La, LIST_INIT_SIZE);
int data[6] = {5,3,6,2,7,4};
for (i=0; i<6;i++) {
insertList(La, data[i], i);
}
printf("LA:\r\n");
printList(La);
deleteListElem(La, 3, e );
printList(La);
insertList(La, e, 3);
printList(La);
//排序
quickSort(La,0, La.lenght-1);
printList(La);
printf("LB:\r\n");
initList(Lb, LIST_INIT_SIZE);
int Bdata[5] = {1,3,2,4,6};
for (i=0; i<5;i++) {
insertList(Lb, Bdata[i], i);
}
//排序
quickSort(Lb,0, Lb.lenght-1);
printList(Lb);
mergeList(La, Lb, Lc);
printList(Lc);
}
3. 線性表的鏈表表示LinkedList
一般使用鏈表來描述。
優點：對于新增和刪除操作add和remove和方便。不需要移動元素。
缺點：不方便隨機訪問元素，LinkedList要移動指針
代碼實現：
// Test.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include <stdio.h>
#include "stdlib.h"
//宏定義
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
#define LT(a,b) ((a)<(b))
#define N = 100
typedef int Status;
typedef int ElemType;
typedef struct LNode{
ElemType data;
struct LNode *next;
}LNode, *LinkList;
/************************************************************************/
/*
初始化鏈表
*/
/************************************************************************/
Status initList(LinkList &L){
/*單鏈表的初始化*/
L = (LinkList)malloc(sizeof(LNode)); //申請一個頭節點
if(!L) exit(OVERFLOW); //申請空間失敗
L->next=NULL; //建立一個帶都節點的空鏈表
return OK;
/*
需要改變指針的指針，所以參數必須是引用或者是 *L:
(*L) = (Lnode *)malloc(sizeof(Lnode));
(*L)->next=NULL;
return 1;
*/
}
/************************************************************************/
/*
創建鏈表
*/
/************************************************************************/
void createList(LinkList L, int n){
/*單鏈表的初始化*/
if (!L) {
initList(L);
}
ElemType data;
LinkList p,q = L;
printf("輸入節點數據的個數%d：\r\n", n);
for(int i = 0; i<n; i++) {
p = (LinkList) malloc( sizeof(LNode)); //申請一個新節點
scanf("%d",&data);
p->data = data;
p->next = q->next;
q->next = p;
q = p;
}
}
/************************************************************************/
/* 在第i位置插入e
*/
/************************************************************************/
Status insertList(LinkList L, ElemType e, int i){
LinkList s, p = L;
int j = 0;
while (p && j<i){ //尋找i節點
p = p->next;
j++;
}
if (!p ||j >i) return ERROR;
s = (LinkList) malloc(sizeof(LNode)); //生成新節點
s->data = e; s->next = p->next; //插入L中
p->next = s;
return OK;
}
/************************************************************************/
/* 刪除第i位置元素，并用e返回其值 */
/************************************************************************/
Status deleteListElem(LinkList L, int i, ElemType &e){
LinkList p, q;
int j = 0;
p = L;
while (p && j<i){
p = p->next;
++j;
}
if (!p->next || j>i) return ERROR; //刪除的位置不對
q = p->next; p->next = q->next;
e = q->data; free(q); //釋放節點
return OK;
}
/************************************************************************/
/* 插入排序
*/
/************************************************************************/
void InsertSort(LinkList L)
{
LinkList list; /*為原鏈表剩下用于直接插入排序的節點頭指針*/
LinkList node; /*插入節點*/
LinkList p;
LinkList q;
list = L->next; /*原鏈表剩下用于直接插入排序的節點鏈表*/
L->next = NULL; /*只含有一個節點的鏈表的有序鏈表。*/
while (list != NULL) { /*遍歷剩下無序的鏈表*/
node = list, q = L;
while (q && node->data > q->data ) {
p = q;
q = q->next;
}
if (q == L) { /*插在第一個節點之前*/
L = node;
} else { /*p是q的前驅*/
p->next = node;
}
list = list->next;
node->next = q; /*完成插入動作*/
}
}
/************************************************************************/
/*
合并兩個線性表
*/
/************************************************************************/
void mergeList(LinkList &La, LinkList &Lb, LinkList &Lc){
LinkList pa, pb, pc;
pa = La->next;
pb = Lb->next;
Lc = pc = La;
while (pa && pa) {
if (pa->data > pb->data) {
pc->next = pb;
pc = pb;
pb =pb->next;
}else{
pc->next = pa;
pc = pa;
pa =pa->next;
}
}
pc->next = pa? pa :pb;
free(Lb);
}
/************************************************************************/
/* 打印list
*/
/************************************************************************/
void printList(LinkList L){
printf("當前值:");
LinkList p;
p = L->next;
while(p){
printf("%d ", p->data);
p = p->next;
}
printf("\r\n");
}
void main()
{
LinkList La,Lb,Lc;
ElemType e;
int init,i;
printf("LA:\r\n");
initList(La);
createList(La, 5);
insertList(La, 7, 3);
printList(La);
deleteListElem(La, 3, e);
printList(La);
InsertSort(La);
printList(La);
printf("Lb:\r\n");
initList(Lb);
createList(Lb, 4);
InsertSort(Lb);
printList(Lb);
printf("Lc:\r\n");
initList(Lc);
mergeList(La, Lb, Lc);
printList(Lc);
}
轉自：http://blog.csdn.net/hguisu/article/details/7673703
原創文章，作者：s19930811，如若轉載，請注明出處：http://www.www58058.com/2804
