blog-hexo/source/_posts/ky/线性表.md

---
title: 线性表
top: 0
categories:
  - 读书
status: doing
use: katex
abbrlink: 1106
---

# 静态初始化

```c
#include<stdio.h>
#define Maxsize 10

typedef struct{
	int data[Maxsize];
	int length;
}SqList;

void InitList(SqList *L){
	for(int i = 0;i < Maxsize;i ++ ){
		L->data[i] = 0;
	}
	L->length = 0;
}

int main(){
	SqList L;
	InitList(&L);
	for(int i = 0;i< Maxsize;i++){
		printf("data[%d]=%d\n",i,L.data[i]);
	} 
	return 0;
} 
```

# 插入数据

```c
#include<stdio.h>
#include<stdlib.h>
#define MaxSize 10

typedef struct{
	int *data;
    int length;
}SeqList;

void ListInsert(SeqList *L,int i,int e){
    for(int j = L->length;j>=i;j--){
        L->data[j] = L->data[j-1];
    }
    L->data[i-1] = e;
    L->length ++;
}
void InitList(SeqList *L){
	L->data = (int*)malloc(sizeof(int)*MaxSize);
    L->length = 0;
}
void PrintList(SeqList L){
	for(int i = 0;i <L.length;i++){
		printf("%d\n",L.data[i]);
    }
}
int main(){
	SeqList L;
    InitList(&L);
    L.data[0] = 0;
    L.length++;
    L.data[1] = 1;
    L.length++;
    L.data[2] = 2;
    L.length++;
    L.data[3] = 3;
    L.length++;
    L.data[4] = 4;
    L.length++;
    PrintList(L);
    ListInsert(&L,3,3);
    PrintList(L);
    return 0;
}
```

# 删除数据

```c
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#define MaxSzie 10

typedef struct{
	int *data;
    int length;
}SeqList;

void InitList(SeqList *L){
    L->data = (int*)malloc(sizeof(int)*MaxSzie);
    L->length = 0;
}

bool InsertList(SeqList *L,int i,int e){
    if(i<1||i>L->length+1){
        return false;
    }
	if(L->length>=MaxSzie){
        return false;
    }
    for(int j = L->length;j>=i;j--){
        L->data[j] = L->data[j-1];
    }
    L->data[i-1] = e;
    L->length++;
    return true;
}

bool DeleteList(SeqList *L,int i,int *e){
	if(i<1||i>L->length){
    	return false;
    }
    *e = L->data[i-1];
    for(int j = i;j<L->length;j++){
        L->data[j-1] = L->data[j]; 
    }
    L->length --;
    return true;
}

void PrintList(SeqList L){
    for(int i = 0;i < L.length;i ++){
        printf("%d\n",L.data[i]);
    }
}

int main(){
    SeqList L;
    InitList(&L);
    for(int i = 0;i < 5; i++){
        InsertList(&L,i,i);
    }
    PrintList(L);
    int e = -1;
    if(DeleteList(&L,3,&e)){
        printf("已删除第3个元素，删除元素值为%d\n",e);
    }
    else{
        printf("位序i不合法，删除失败\n");
    }
    PrintList(L);
    return 0;
}
```

# 静态线性表按位查找

```c
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#define MaxSize 10

typedef struct{
	int data[MaxSize];
    int length;
}SeqList;

void InitList(SeqList *L){
    for(int i = 0;i < MaxSize;i ++){
        L->data[i] = 0;
    }
    L->length = 0;
}

void InsertList(SeqList *L,int i ,int e){
    L->data[i] = e;
    L->length ++;
}
int GetElement(SeqList L,int i){
    return L.data[i-1];
}

int main(){
    SeqList L;
    InitList(&L);
	for(int i = 0;i < 9; i++){
        InsertList(&L,i,i);
    }
	printf("%d\n",GetElement(L,5));
    return 0;
}
```

# 动态初始化

```c
#include<stdio.h>
#include<stdlib.h>
#define InitSize 10

typedef struct{
	int *data;
    int MaxSize;
    int length;
}SeqList;
void InitList(SeqList *L){
	L->data = (int*)malloc(sizeof(int)*InitSize);
    L->length = 0;
    L->MaxSize = InitSize;
}
void IncreaseSize(SeqList *L,int len){
    int *p = L->data;
    L->data = (int*)malloc(sizeof(int)*(InitSize+len));
    for(int i = 0;i < L->length;i ++){
        L->data[i] = p[i];
    }
    L->MaxSize = L->MaxSize + len;
    free(p);
}
int main(){
    SeqList L;InitList(&L);
    printf("线性表原长度：%d",L.MaxSize);
    IncreaseSize(&L,5);
    printf("线性表扩容后长度：%d",L.MaxSize);
    return 0;
}
```

# 动态线性表按值查找

```c
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#define InitSize 16

typedef struct{
	int *data;
    int MaxSize;
    int length;
}SeqList;

void InitList(SeqList *L){
    L->data = (int*)malloc(sizeof(int)*InitSize);
    for(int i = 0; i < L->length;i ++){
        L->data[i] = 0;
    }
    L->MaxSize = InitSize;
    L->length = 0;
}

int GetElement(SeqList L,int e){
    for(int i = 0;i < L.length;i ++){
        if(L.data[i]==e){
            return i+1;
        }
    }
    return 0;
}
bool InsertList(SeqList *L,int i,int e){
    if(i<1||i>L->length+1){
        return false;
    }
	if(L->length>=L->MaxSize){
        return false;
    }
    for(int j = L->length;j>=i;j--){
        L->data[j] = L->data[j-1];
    }
    L->data[i-1] = e;
    L->length++;
    return true;
}
int main(){
	SeqList L;
    InitList(&L);
    for(int i = 1;i < 9; i++){
        InsertList(&L,i,i-1);
    }
    printf("查找到的结果为%d",GetElement(L,5));
    return 0;
}
```

# 动态线性表按位查找

```c
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#define InitSize 10

typedef struct{
	int *data;
    int MaxSize;
    int length;
}SeqList;

void InitList(SeqList *L){
	L->data = (int*)malloc(sizeof(int)*InitSize);
    for(int i = 0;i < InitSize;i ++){
        L->data[i] = 0;
    }
    L->MaxSize = InitSize;
    L->length = 0;
}

int GetElement(SeqList L,int i){
    return L.data[i-1];
}

bool InsertList(SeqList *L,int i,int e){
    if(i<1||i>L->length+1){
        return false;
    }
	if(L->length>=L->MaxSize){
        return false;
    }
    for(int j = L->length;j>=i;j--){
        L->data[j] = L->data[j-1];
    }
    L->data[i-1] = e;
    L->length++;
    return true;
}
void PrintList(SeqList L){
    for(int i = 0;i < L.length;i ++){
        printf("%d\n",L.data[i]);
    }
}

int main(){
	SeqList L;
    InitList(&L);
    for(int i = 1;i < 10;i ++){
        InsertList(&L,i,i-1);
    }
    PrintList(L);
    printf("查找到的结果为%d",GetElement(L,6));
    return 0;
}
```