线性结构：
①存在一个唯一的被称为“第一个”的数据元素；
②存在一个唯一的被称为“最后一个”的数据元素；
③除第一个元素外，每个元素均有唯一一个直接前驱；
④除最后一个元素外，每个元素均有唯一一个直接后继
线性表(Linear List) ：
是由n(n≧0)个数据元素(结点)a1，a2，…an组成的有限序列。该序列中的所有结点具有相同的数据类型。其中数据元素的个数n称为线性表的长度。
当n=0时，称为空表。
当n>0时，将非空的线性表记作：(a1，a2，…an) ，a1称为线性表的第一个(首)结点，an称为线性表的最后一个(尾)结点。
顺序存储：把线性表的结点按逻辑顺序依次存放在一组地址连续的存储单元里。
#ifndef _TYPE_H_
#define _TYPE_H_ #include<stdio.h>
#include<stdlib.h>
#include<string.h> #define TRUE 1
#define FALSE 0
#define INIT_SIZE 20
#define INCREMENT 10
#define OVERFLOW -2 typedef int Boolean;
typedef char ElemType; #endif
type.h
/********************************************************
Author: ydp Version: 1.0 Date: 2013/05/03
File name: SqList.c
Description:
sequence list.
Function List:
init():
History:
none
*********************************************************/
#include "type.h" typedef struct ArrayList
{
ElemType *elem;
int length;
int size;
}SqList; Boolean initList(SqList *L);
Boolean insertList(SqList *L,ElemType elem, int pos);
Boolean delList(SqList *L,int pos);
Boolean updateList(SqList *L,ElemType elem, int pos);
int findList(SqList *L,ElemType elem);
Boolean destroyList(SqList *L); int main(void)
{
SqList L,*p;
p=&L;
Boolean flag = initList(&L);
ElemType e = 'y';
flag = insertList(&L,e,);
e = 'p';
insertList(&L,e,);
e = 'd';
insertList(&L,e,);
printf("before delete:\t%s\n",p->elem);
delList(&L,);
printf("L->elem:\t%s\n",p->elem);
printf("L->elem[0]:\t%c\n",p->elem[]);
printf("L->size:\t%d\n",p->size);
printf("L->length:\t%d\n",p->length);
insertList(&L,e,);
updateList(&L,'y',);
printf("after update:\t%s\n",p->elem);
int pos = findList(&L,'p');
printf("pos:\t%d\n",pos);
destroyList(&L);
if(p->elem==NULL)
{
printf("L->elem==NULL\n");
}
return ;
} Boolean initList(SqList *L)
{
printf("Init sqList start!\n");
L->elem = (ElemType *)malloc(INIT_SIZE*sizeof(ElemType));
if(L->elem==NULL)
{
printf("Init sqList false!\n");
exit(OVERFLOW);
} L->length = ;
L->size = INIT_SIZE;
printf("Init sqList success!\n");
return TRUE;
} Boolean insertList(SqList *L,ElemType elem,int pos)
{
printf("Insert list start!\n");
if(L->elem==NULL)
{
printf("List is not init!\n");
initList(L);
}else if(L->length >= L->size)
{
L->elem = (ElemType *) realloc (L->elem,(L->size+INCREMENT)*sizeof(ElemType));
L->size = L->size + INCREMENT;
if(L->elem == NULL)
{
exit(OVERFLOW);
}
}
if(pos< || pos > L->length+)
{
printf("Error position!");
return FALSE;
}
if(L->length > )
{
int len=L->length-;
for(len ; len>=pos- ; len--){
L->elem[len+]=L->elem[len];
}
}
L->elem[pos-] = elem;
++L->length;
printf("Insert list success: %c\n",elem);
return TRUE;
} Boolean delList(SqList *L, int pos)
{
if(pos > L->length || pos < )
{
printf("del error position!");
return FALSE;
}
for(;pos<=L->length;pos++)
{
L->elem[pos-]=L->elem[pos];
}
L->length--;
return TRUE;
}
Boolean updateList(SqList *L,ElemType elem, int pos)
{
if(pos< || pos >= L->length)
{
printf("Update elem error place!");
return FALSE;
}
L->elem[pos-]=elem;
return TRUE;
} int findList(SqList *L,ElemType elem)
{
if(L->elem == NULL)
{
return -;
}
int i=;
for(;i<L->length;i++)
{
if(elem == L->elem[i])
return i+;
}
return -;
} Boolean destroyList(SqList *L)
{
if(L->elem)
{
free(L->elem);
L->elem=NULL;
printf("Destroy line list success! \n");
}
}
SqList.c
链式存储：
#ifndef _LIST_H_
#define _LIST_H_ #define TRUE 1
#define FALSE 0
#define OVERFLOW -2 typedef int Boolean;
typedef char ElemType; typedef struct ListNode
{
ElemType elem;
struct ListNode *next;
}LNode; Boolean isEmpty(LNode *node);
void print(LNode *node);
void addList_tail(LNode *node,int num);
void addList_head(LNode *node,int num);
ElemType getElem(LNode *L,int i);
int locateElem(LNode *L, ElemType key);
Boolean insertElem(LNode *L, ElemType key, int addr);
Boolean modifyElem(LNode *L, ElemType key, int addr);
Boolean deleteElem(LNode *L, int addr);
#endif
list.h
#include"list.h"
#include<stdio.h>
#include<stdlib.h> int main(void)
{
LNode *p,*head;
head=p=(LNode *)malloc(sizeof(LNode));
head->next=NULL;
if(isEmpty(p)){
printf("List is null\n");
}else {
printf("List is not null\n");
}
addList_tail(head,);
// addList_head(head,5);
print(head);
ElemType e = getElem(head,);
printf("getElem(2)=%c\n",e);
int add = locateElem(head,'f');
printf("locateElem(f)=%d\n",add);
if(insertElem(head,'i',)){
printf("insert(head,'i',2) sucess!\n");
}else{
printf("insert(head,'i',2) fail!\n");
}
print(head);
if(modifyElem(head,'h',)){
printf("modifyElem(head,'h',1) success! \n");
}else{
printf("modifyElem(head,'h',1) success! \n");
}
print(head);
if(deleteElem(head,)){
printf("deleteElem(head,1) sucess!\n");
}else{
printf("deleteElem(head,1) sucess!\n");
}
print(head);
} Boolean isEmpty(LNode *node){
if(node->next != NULL){
return FALSE;
}
return TRUE;
} void print(LNode *node){
while(node->next != NULL){
node=node->next;
printf("elem:%c\n",node->elem);
}
} void addList_tail(LNode *node,int num){
LNode *p,*q;
int i;
p=node;
char e;
printf("will input %d elem!",num);
for(i=;i<=num;i++){
q=(LNode *)malloc(sizeof(LNode));
printf("\nplease input the %dth elem:",i);
scanf("%c",&e);
//The follow 2line is clear ‘'\n' in memery
int c;
while ((c=getchar()) != '\n' && c != EOF);
//fflush(stdin);
q->elem=e;
q->next=p->next;
p->next=q;
p=q;
}
} void addList_head(LNode *node,int num){
LNode *p,*q;
int i;
p=node;
char e;
printf("will input %d elem!",num);
for(i=;i<=num;i++){
q=(LNode *)malloc(sizeof(LNode));
printf("\nplease input the %dth elem:",i);
scanf("%c",&e);
int c;
while ((c=getchar()) != '\n' && c != EOF);
q->elem=e;
q->next=p->next;
p->next=q;
//p=q;
}
} ElemType getElem(LNode *L,int i)
{
int count=;
LNode *p;
p=L;
for(;count<i;count++)
{
if(p->next!=NULL){
p=p->next;
}
else
{
printf("out of boundry!");
return ;
}
} return p->elem;
} int locateElem(LNode *L, ElemType key)
{
int count=;
LNode *p;
p=L;
while(p->next != NULL)
{
p=p->next;
count++;
if(p->elem == key)
return count;
}
return -;
} Boolean insertElem(LNode *L, ElemType key, int addr)
{
LNode *p,*q;
p = L;
int count;
for(count=;count<addr;count++)
{
if(p->next != NULL)
p=p->next;
else
{
printf("Wrong addr!");
return FALSE;
}
}
q=(LNode *)malloc(sizeof(LNode));
q->next = p->next;
p->next = q;
q->elem = key; return TRUE;
}
Boolean modifyElem(LNode *L, ElemType key, int addr)
{
LNode *p;
p=L;
int count;
for(count=;count<addr;count++)
{
if(p->next != NULL)
p=p->next;
else
{
printf("Wrong addr!");
return FALSE;
}
}
p->elem = key;
return TRUE;
}
Boolean deleteElem(LNode *L, int addr)
{
LNode *p,*q;
p=L;
int count;
for(count=;count<addr-;count++)
{
if(p->next != NULL)
p=p->next;
else
{
printf("Wrong addr!");
return FALSE;
}
}
q = p->next;
p->next = q->next;
free(q);
return TRUE;
}
list.c