線性表(Linear List):由同類型數(shù)據(jù)元素構(gòu)成有序序列的線性結(jié)構(gòu)
- 表中元素個數(shù)稱為線性表的長度
- 線性表沒有元素時，稱為空表
- 表起始位置稱表頭分尸，表結(jié)束位置稱表尾
1. 線性表順序存儲實現(xiàn)
-
利用數(shù)組的連續(xù)存儲空間存放線性表的順序元素锦聊。
typedef struct {
ElementType data[MAXSIZE];
int last;
} SqList;
主要操作
1.初始化（建立空順序表）
SqList* makeEmpty()
{
SqList *ptrL;
ptrL = (SqList *)malloc(sizeof(Sqlist));
ptrL->last = -1;
return ptrL;
}
2. 查找
int find(ElementType x, SqList *ptrL)
{
int i = 0;
while(i < ptrL->last && ptrL->data[i]!=x)
i++;
if(i > ptrl->last)
return -1;
else
return i;;
}
3. 插入操作
void insert(ElementType x, int i, SpList *ptrL)
{
int j;
if(ptrL->last == MAXSIZE - 1){
printf("表滿");
return;
}
if(i < 0 || i > ptrL->last + 1){
printf("位置不合法");
return;
}
for(j = ptrL->last; j >= i; j--)
ptrL->data[j+1] = ptrL->data[j];
ptrL->data[i] = x;
ptrL->last++;
}
4. 刪除
void delete(int i, SqList *ptrL)
{
int j;
if(i < 0 || i > ptrL->last){
print("不存在第%d個元素",i);
return;
}
for (j = i; j < ptrL->last; j++) {
ptrL->data[j] = ptrL->data[j+1];
}
ptrL->last--;
}
2. 線性表鏈?zhǔn)酱鎯崿F(xiàn)
- 不要求邏輯上相鄰的兩個節(jié)點(diǎn)物理上也相鄰，通過“鏈”建立起數(shù)據(jù)元素之間的邏輯關(guān)系箩绍。
-
插入孔庭、刪除不需要移動數(shù)據(jù)元素，只需要修改“鏈”材蛛。
struct LNode{
ElementType data,
struct LNode *next;
}
typedef struct LNode* List
主要操作
1. 求表長
int length(List ptrL)
{
List p = ptrL;
int j = 0;
while (p) {
p = p->next;
j++
}
return j;
}
2. 查找
(1) 按序號查詢
List FindKth(int k, List ptrL)
{
List p = ptrL;
int i = 0;
while (p != NULL && i < k) {
p = p->next;
i++;
}
if(i == k)
return p;
else
return NULL;;
}
(2) 安值查找
List Find(ElementType x, List ptrL)
{
List p = ptrL;
while (p!=NULL && p->data!=x) {
p = p->next;
}
return p;
}
3. 插入
List insert(ElementType x, int i, List ptrL)
{
List p, s;
if(i == 0){
s = (List)malloc(sizeof((struct LNode)));
s -> data = x;
s -> next = ptrL;
return s;
}
p = FindKth(i-1,ptrL);
if(p == NULL){
printf("參數(shù)i有誤");
return NULL;
}else{
s = (List)malloc(sizeof((struct LNode)));
s -> data = x;
s -> next = p -> next;
p -> next = s;
return ptrL;
}
}
4. 刪除
List delete(int i,List ptrL)
{
List p, s;
if(i == 0){
s = ptrL;
if(ptrL != NULL)
ptrL = ptrL -> next;
free(s);
return ptrL;
}
p = FindKth(i - 1,ptrL);
if(p == NULL){
printf("第%d個節(jié)點(diǎn)不存在",i-1);
return NULL;
}else if (p->next == NULL){
printf("第%d個節(jié)點(diǎn)不存在",i);
return NULL;
}else{
s = p->next;
p->next = s->next;
free(s);
return ptrL;
}
}
3. 線性表靜態(tài)鏈表存儲方式
靜態(tài)鏈表：為了和指針型描述的線性表相區(qū)別圆到，我們給這種用數(shù)組描述的鏈表叫做靜態(tài)鏈表
多項式表示方法
3. 鏈表逆轉(zhuǎn)算法
為了方便，我們添加了一個頭結(jié)點(diǎn)卑吭。我們逆序其中的一部分芽淡。我們需要三個指針：new old tmp. 在將old指向new的時候需要用tmp記錄old next. 要不然就找不到old next了 將old->next = new, 然后new = old, old = tmp, tmp = old->next,依次類推。
end:逆序的最大索引
List reverseList(List ptrL, int end)
{
if(ptrL == NULL){
printf("鏈表有誤");
return NULL;
}
if(end + 1 > length(ptrL))
{
printf("end索引有誤");
return ptrL;
}
List new = ptrL, old = ptrL->next, tmp = old->next;
int last = 1;
while (old && last <= end) {
old->next = new;
new = old;
old = tmp;
tmp = tmp != NULL ? tmp->next : tmp;
last++;
}
ptrL->next = old;
ptrL = new;
return ptrL;
}
