当前位置：首页 > news >正文

数据结构(二) 线性表

news 来源：原创 2024/5/10 10:10:55

一、线性表的定义

　　线性表是最基本、最简单、也是最常用的一种数据结构。线性表（linear list）是数据结构的一种，一个线性表是n个具有相同特性的数据元素的有限序列。

　　线性表主要由顺序表示或链式表示。在实际应用中，常以栈、队列、字符串等特殊形式使用。顺序表示指的是用一组地址连续的存储单元依次存储线性表的数据元素，称为线性表的顺序存储结构或顺序映像。链式表示指的是用一组任意的存储单元存储线性表中的数据元素，称为线性表的链式存储结构。

二、顺序表

#include<stdio.h>
#include <cstdlib>

#define MAXSIZE 100
typedef int datatype;
typedef struct {
    datatype a[MAXSIZE];
    int size;
}sequence_list;

/*
 * 初始化表
 */
void init(sequence_list *slt) {
    slt->size = 0;
}

/*
 * 在顺序表后进行添加操作
 */
void append(sequence_list *slt, datatype x) {
    if(slt->size == MAXSIZE) {
        printf("顺序表是满的!\n");
        exit(1);
    }
    slt->a[slt->size] = x;
    slt->size++;
}

/*
 * 打印顺序表
 */
void display(sequence_list slt) {
    if(!slt.size) printf("顺序表为空!\n");
    else {
        printf("顺序表的各个结点的值为:\n");
        for(int i = 0; i < slt.size; i++) printf("%5d", slt.a[i]);
        printf("\n");
    }
}

/*
 * 判断顺序表是否为空
 */
int empty(sequence_list stl) {
    return stl.size == 0 ? 1 : 0;
}

/*
 * 查找顺序表中值为x的结点操作
 */
int find(sequence_list stl, datatype x) {
    int i = 0;
    while(i < stl.size && stl.a[i] != x) i++;
    return i < stl.size ? i : -1;
}

/*
 * 取得顺序表中第i个结点的值
 */
int get(sequence_list stl, int i) {
    if(i < 0 || i >= stl.size) {
        printf("i值不合法!\n");
        exit(1);
    }
    return stl.a[i];
}

/*
 * 在顺序表的position位置插入值为x的结点
 */
void insert(sequence_list *slt, int position, datatype x) {
    int i;
    if(slt->size == MAXSIZE) {
        printf("顺序表是满的，无法插入!\n");
        exit(1);
    }
    if(position < 0 || position > slt->size) {
        printf("position不合法!\n");
        exit(1);
    }
    for(int i = slt->size; i > position; i--) slt->a[i] = slt->a[i-1];
    slt->a[position] = x;
    slt->size++;
}

/*
 * 删除顺序表中第position位置的结点
 */
void dele(sequence_list *slt, int position) {
    int i;
    if(slt->size == 0) {
        printf("顺序表为空!\n");
        exit(1);
    }
    if(position < 0 && position >= slt->size) {
        printf("position不合法!\n");
        exit(1);
    }
    for (int i = position; i < slt->size - 1; i++) slt->a[i] = slt->a[i+1];
    slt->size--;
}

/*
 * 测试
 */
int main() {
    sequence_list stl;
    init(&stl);
    append(&stl, 1);
    append(&stl, 2);
    append(&stl, 3);
    dele(&stl, 1);
    insert(&stl, 2, 4);
    display(stl);
    return 0;
}

View Code

三、链表

　　3.1、不带头结点的单链表

#include<stdio.h>
#include <cstdlib>

typedef int datatype;
typedef struct link_node{
    datatype info;
    struct link_node *next;
}node;

/*
 * 创建一个空链表
 */
node* init() {
    return NULL;
}

/*
 * 遍历该链表
 */
void display(node *head) {
    node *p;
    p = head;
    if(!p) printf("单链表为空！\n");
    else {
        printf("单链表的各个结点的值为:\n");
        while(p) {
            printf("%5d", p->info); p = p->next;
        }
        printf("\n");
    }
}

/*
 * 查找单链表中第i个结点
 */
node* find(node *head, int i) {
    int j = 1;
    node *p = head;
    if(i < 1) return NULL;
    while(p && i != j) {
        p = p->next;
        j++;
    }
    return p;
}
/*
 * 在第i个结点后插入一个值为x的结点
 */
node *insert(node *head, int i, datatype x) { ;
    node *q = find(head, i);
    if(!q && i!= 0) printf("找不到第%d个结点,无法插入%d！\n", i, x);
    else {
        node *p = (node*)malloc(sizeof(node));
        p->info = x;
        if(i == 0) {
            p->next = head;
            head = p;
        } else {
            p->next = q->next;
            q->next = p;
        }
    }
    return head;
}

/*
 * 删除一个值为x的结点
 */
node *dele(node *head, datatype x) {
    node *pre = NULL;
    if(!head) {
        printf("单链表为空！\n");
        return head;
    }
    node *p = head;
    while(p && p->info != x) {
        pre = p;
        p = p->next;
    }
    if(p){
        if(!pre) head = head->next;
        else pre->next = p->next;
        free(p);
    }
    return head;
}

/*
 * 测试
 */
int main() {
    node *head = init();
    dele(head, 1);
    head = insert(head, 0, 5);
    head = insert(head, 1, 6);
    display(head);
    head = dele(head, 5);
    display(head);
    printf("%d", find(head, 1)->info);
    return 0;
}

View Code

　　3.2、带头结点的单链表

#include<stdio.h>
#include<stdlib.h>

typedef int datatype;
typedef struct link_node{
    datatype info;
    struct link_node *next;
}node;

/*
 * 建立一个空的带头结点的单链表
 */
node *init() {
    node *head = (node*)malloc(sizeof(node));
    head->next = NULL;
    return head;
}

/*
 * 输出带头结点的单链表中各个结点的值
 */
void display(node *head) {
    node *p;
    p = head->next;
    if(!p) printf("\n带头结点的单链表是空的!");
    else {
        printf("\n带头结点的单链表各个结点的值为：\n");
        while(p) { 
            printf("%5d", p->info);
            p=p->next;
        }
    }
}

/*
 * 在带头结点的单链表中查找第i个结点地址
 */
node *find(node *head, int i) {
    int j = 0;
    node *p = head;
    if(i<0){
        printf("\n带头结点的单链表中不存在第%d个结点！", i);
        return NULL;
    }
    else if(i == 0) return p;
    while(p && i != j){
        p = p->next;
        j++;
    }
    return p;
}

/*
 * 在带头结点的单链表中第i个结点后插入一个值为x的新结点
 */
node *insert(node *head, int i, datatype x)
{
    node *q = find(head, i);
    if(!q) {
        printf("\n带头结点的单链表中不存在第%d个结点！不能插入%d！", i, x);
        return head;
    }
    node *p = (node*)malloc(sizeof(node));
    p->info = x;
    p->next = q->next;
    q->next = p;
    return head;
}

/*
 * 函数功能：在带头结点的单链表中删除一个值为x的结点
 */
node *dele(node *head, datatype x)
{
    node *pre = head,*q;
    q = head->next;
    while(q && q->info != x) {
        pre = q;
        q = q->next;
    }
    if(q) {
        pre->next = q->next;
        free(q);
    }
    return head;
}

/*
 * 测试
 */
int main() {
    node *head = init();
    insert(head, 0, 1);
    insert(head, 1, 2);
    insert(head, 1, 3);
    dele(head, 2);
    display(head);
    return 0;
}

View Code

　　3.3、循环单链表

#include<stdio.h>
#include<stdlib.h>

typedef int datatype;
typedef struct link_node{
    datatype info;
    struct link_node *next;
}node;

/*
 * 建立一个空的循环单链表
 */
node *init() {
    return NULL;
}

/*
 * 获得循环单链表的最后一个结点的地址
 */
node* rear(node *head) {
    node *p;
    if(!head) p = NULL;
    else {
        p = head;
        while(p->next != head) p = p->next;
    }
    return p;
}

/*
 * 输出循环单链表中各个结点的值
 */
void display(node *head) {
    node *p;
    if(!head) printf("循环单链表为空!\n");
    else {
        printf("循环单链表各个结点的值为：\n");
        printf("%5d", head->info);
        p = head->next;
        while(p != head) {
            printf("%5d", p->info);
            p = p->next;
        }
        printf("\n");
    }
}

/*
 * 在循环单链表中查询一个值为x的结点
 */
node *find(node *head, datatype x) {
    node *q;
    if(!head) {
        printf("循环单链表为空，无法找到指定结点！");
        return NULL;
    }
    q = head;
    while(q->next != head && q->info != x) q = q->next;
    if(q->info == x) return q;
    else return NULL;
}

/*
 * 在循环单链表中第i个结点后插入一个值为x的新结点
 */
node *insert(node *head, int i, datatype x)
{
    node *p = (node*)malloc(sizeof(datatype));
    p->info = x;
    if(i < 0) {
        printf("i值不合法！\n");
        free(p);
        return head;
    }
    if(!i && !head) {
        p->next = p;
        head = p;
        return head;
    }
    if(!i && head) {
        node *myrear = rear(head);
        p->next = head;
        head = p;
        myrear->next = p;
        return head;
    }
    if(i > 0 && !head) {
        printf("i值不合法！\n");
        free(p);
        return head;
    }
    if(i > 0 && head) {
        node *q = head;
        int j = 1;
        while(i != j && q->next != head) {
            q = q->next;
            j++;
        }
        if(i != j) {
            printf("i值不合法！\n");
            free(p);
            return head;
        } else {
            p->next = q->next;
            q->next = p;
            return head;
        }
    }
}

/*
 * 函数功能：在循环单链表中删除一个值为x的结点
 */
node *dele(node *head,datatype x){
    node *pre = NULL;
    if(!head){
        printf("循环单链表为空，无法做删除操作！\n");
        return head;
    }
    node *q = head;
    while(q->next != head && q->info != x){
        pre = q;
        q = q->next;
    }
    if(q->info != x){
        printf("没有找到值为%d的结点!\n",x);
    }
    else {
        if (q != head) {
            pre->next = q->next;
            free(q);
        } else {
            if (head->next == head) {
                free(q);
                head = NULL;
            } else {
                node *myrear = rear(head);
                head = head->next;
                myrear->next = head;
                free(q);
            }
        }
    }
    return head;
}

/*
 * 测试
 */
int main() {
    node *head = init();
    head = insert(head, 0, 1);
    head = insert(head, 1, 2);
    head = insert(head, 1, 3);
    display(head);
    head = dele(head, 1);
    display(head);
    return 0;
}

View Code

　　3.4、双链表

#include<stdio.h>
#include<stdlib.h>

typedef int datatype;
typedef struct dlink_node{
    datatype info;
    struct dlink_node *llink, *rlink;
}dnode;

/*
 * 创建一个空的双链表
 */
dnode *init(){
    return NULL;
}

/*
 * 函数功能：输出双链表中各个结点的值
 */
void display(dnode *head)
{
    dnode *p;
    p=head;
    if(!p) printf("双链表是空的!\n");
    else {
        printf("双链表中各个结点的值为：\n");
        while(p) {
            printf("%5d", p->info);
            p=p->rlink;
        }
        printf("\n");
    }
}

/*
 * 在双链表中查找第i个结点的存储地址
 */
dnode *find(dnode *head, int i)
{
    int j = 1;
    dnode *p = head;
    if(i < 1) {
        printf("第%d个结点不存在!\n", i);
        return NULL;
    }
    while(p && i != j) {
        p=p->rlink;
        j++;
    }
    if(!p){
        printf("第%d个结点不存在!\n", i);
        return NULL;
    }
    return p;
}

/*
 * 双链表第i个结点后插入值为x的新结点
 */
dnode *insert(dnode *head, int i, datatype x)
{
    dnode *p = (dnode*)malloc(sizeof(dnode));
    p->info = x;
    if(!i){
        p->llink = NULL;
        p->rlink = head;
        if (!head) { /*在双链表为空情况下的在首部插入一个结点*/
            head = p;
        }
        else { /*在双链表不为空情况下在首部插入一个结点*/
            head->llink = p;
            head = p;
        }
        return head;
    }
    dnode *q = find(head, i);
    if(!q) {
        printf("第%d个结点不存在，无法进行插入\n", i);
        free(p);
        return head;
    }
    if(q->rlink == NULL) { /*在最后一个结点后插入*/
        p->rlink = q->rlink;
        p->llink = q;
        q->rlink=p;
    }
    else { /*一般情况下的插入*/
        p->rlink=q->rlink;
        p->llink=q;
        q->rlink->llink=p;
        q->rlink=p;
    }
    return head;
}

/*
 * 在双链表中删除一个值为x的结点
 */
dnode *dele(dnode *head,datatype x)
{
    if(!head) {
        printf("双链表为空，无法进行删除操作\n");
        return head;
    }
    dnode *q = head;
    while(q && q->info != x) q=q->rlink;
    if(!q) {
        printf("没有找到值为%d的结点！不做删除操作！\n", x);
    }
    if(q == head && head->rlink){ /*被删除的结点是第一个结点并且表中不只一个结点*/
        head = head->rlink;
        head->llink = NULL;
        free(q);
        return head;
    }
    if(q == head && !head->rlink) { /*被删除的结点是第一个结点并且表中只有这一个结点*/
        free(q);
        return NULL;
    }
    else {
        if(!q->rlink) {/*被删除的结点是双链表中的最后一个结点*/
            q->llink->rlink = NULL;
            free(q);
            return head;
        }
        else {   /*q是有2个以上结点的双链表中的一个非开始、也非终端结点*/
            q->llink->rlink = q->rlink;
            q->rlink->llink = q->llink;
            free(q);
            return head;
        }
    }
}

/*
 * 测试
 */
int main() {
    dnode *head = init();
    head = insert(head, 0, 1);
    head = insert(head, 1, 2);
    head = insert(head, 1, 3);
    display(head);
    head = dele(head, 1);
    display(head);
    return 0;
}

View Code

四、栈

　　4.1、顺序栈

#include <stdio.h>
#include <cstdlib>

#define MAXSIZE 100
typedef int datatype;
typedef struct {
    datatype a[MAXSIZE];
    int top;
}sequence_stack;

/*
 * 栈初始化
 */
void init(sequence_stack *st) {
    st->top = 0;
}

/*
 * 判断栈是否为空
 */
int empty(sequence_stack st) {
    return st.top ? 0 : 1;
}

/*
 * 读取栈顶的值
 */
datatype read(sequence_stack st) {
    if(empty(st)) {
        printf("栈是空的！\n");
        exit(1);
    }
    else {
        return st.a[st.top-1];
    }
}

/*
 * 栈的插入操作
 */
void push(sequence_stack *st, datatype x) {
    if(st->top == MAXSIZE) {
        printf("栈满了\n");
        exit(1);
    }
    st->a[st->top] = x;
    st->top++;
}

/*
 * 栈的删除操作
 */
void pop(sequence_stack *st) {
    if(st->top == 0) {
        printf("栈为空！\n");
        exit(1);
    }
    st->top--;
}

/*
 * 测试
 */
int main() {
    sequence_stack st;
    init(&st);
    push(&st, 1);
    push(&st, 2);
    push(&st, 3);
    pop(&st);
    printf("%d\n", read(st));
}

View Code

　　4.2、链表栈

#include <stdio.h>
#include <cstdlib>

typedef int datatype;
typedef struct link_stack {
    datatype info;
    struct  link_stack *next;
} node;

/*
 * 建立一个空栈
 */
node* init() {
    return  NULL;
}

/*
 * 判断链式栈是否为空
 */
int empty(node *top) {
    return  top ? 0 : 1;
}

/*
 * 读取链式栈栈顶结点
 */
datatype read(node *top) {
    if(empty(top)) {
        printf("栈是空的！\n");
        exit(1);
    }
    return  top->info;
}

/*
 * 输出链式栈各个结点的值
 */
void display(node *top) {
    if(empty(top)) printf("栈是空的！\n");
    node *p = top;
    while(p) {
        printf("%5d", p->info);
        p = p->next;
    }
    printf("\n");
}

/*
 * 进栈
 */
node *push(node *top, datatype x) {
    node *p = (node*)malloc(sizeof(node));
    p->info = x;
    p->next = top;
    top = p;
    return top;
}

/*
 * 出栈
 */
node *pop(node *top) {
    if(empty(top)) {
        printf("栈是空的！\n");
        return NULL;
    }
    node *q = top;
    top = top->next;
    free(q);
    return top;
}

/*
 * 测试
 */
int main() {
    node *top = init();
    top = push(top, 1);
    top = push(top, 2);
    top = push(top, 3);
    top = pop(top);
    display(top);
    printf("%d", read(top));
    return 0;
}

View Code

五、队列

　　5.1、顺序队列

#include <stdio.h>
#include <cstdlib>

#define MAXSIZE 100
typedef int datatype;
typedef struct {
    datatype a[MAXSIZE];
    int front;
    int rear;
}sequence_queue;

/*
 * 顺序队列初始化
 */
void init(sequence_queue *sq) {
    sq->front = sq->rear = 0;
}

/*
 * 判断栈顺序队列是否为空
 */
int empty(sequence_queue sq) {
    return sq.front == sq.rear ? 1 : 0;
}

/*
 * 打印顺序队列各个结点的值
 */
void display(sequence_queue sq) {
    if(empty(sq)) printf("顺序队列为空！\n");
    else {
        for(int i = sq.front; i < sq.rear; i++) printf("%5d", sq.a[i]);
        printf("\n");
    }
}

/*
 * 取得队首结点值
 */
datatype get(sequence_queue sq) {
    if(empty(sq)) {
        printf("顺序队列为空！\n");
        exit(1);
    }
    return sq.a[sq.front];
}

/*
 * 队列的插入操作
 */
void insert(sequence_queue *sq, datatype x) {
    if(sq->rear == MAXSIZE) {
        printf("顺序队列为满！\n");
        exit(1);
    }
    sq->a[sq->rear] = x;
    sq->rear++;
}

/*
 * 队列的删除操作
 */
void dele(sequence_queue *sq) {
    if(empty(*sq)) {
        printf("顺序队列为空！,不能进行删除操作\n");
        exit(1);
    }
    sq->front++;
}

/*
 * 测试
 */  
int main() {
    sequence_queue sq;
    init(&sq);
    insert(&sq, 1);
    insert(&sq, 2);
    insert(&sq, 3);
    printf("%d\n", get(sq));
    dele(&sq);
    display(sq);
    return 0;
}

View Code

　　5.2、顺序循环队列

#include <stdio.h>
#include <cstdlib>

#define MAXSIZE 100
typedef int datatype;
typedef struct {
    datatype a[MAXSIZE];
    int front;
    int rear;
}sequence_cqueue;

/*
 * 顺序循环队列初始化
 */
void init(sequence_cqueue *sq) {
    sq->front = sq->rear = 0;
}

/*
 * 判断顺序循环队列是否为空
 */
int empty(sequence_cqueue sq) {
    return sq.front == sq.rear ? 1 : 0;
}

/*
 * 打印顺序循环队列各个结点的值
 */
void display(sequence_cqueue sq) {
    if(empty(sq)) printf("顺序队列为空！\n");
    else {
        for(int i = sq.front; i < sq.rear; i++) printf("%5d", sq.a[i]);
        printf("\n");
    }
}

/*
 * 取得队首结点值
 */
datatype get(sequence_cqueue sq) {
    if(empty(sq)) {
        printf("顺序队列为空！\n");
        exit(1);
    }
    return sq.a[sq.front];
}

/*
 * 顺序循环队列的插入操作
 */
void insert_cqueue(sequence_cqueue *sq, datatype x) {
    if((sq->rear+1)%MAXSIZE == sq->front) {
        printf("队列是满的！\n");
        exit(1);
    }
    sq->a[sq->rear] = x;
    sq->rear = (sq->rear+1) % MAXSIZE;
}

/*
 * 顺序循环队列的删除操作
 */
void dele_cqueue(sequence_cqueue *sq) {
    if(empty(*sq)) {
        printf("队列为空！,不能进行删除操作\n");
        exit(1);
    }
    sq->front = (sq->front + 1) % MAXSIZE;
}

int main() {
    sequence_cqueue sq;
    init(&sq);
    insert_cqueue(&sq, 1);
    insert_cqueue(&sq, 2);
    insert_cqueue(&sq, 3);
    printf("%d\n", get(sq));
    dele_cqueue(&sq);
    display(sq);
    return 0;
}

View Code

　　5.3、链式队列

#include <stdio.h>
#include <cstdlib>

typedef int datatype;
typedef struct link_node {
    datatype info;
    struct link_node *next;
}node;
typedef struct {
    node *front, *rear;
}queue;

/*
 * 建立一个空的链式队列
 */
queue *init() {
    queue *qu = (queue*)malloc(sizeof(queue));
    qu->front = NULL;
    qu->rear = NULL;
    return qu;
}

/*
 * 判断链式队列是否为空
 */
int empty(queue *qu) {
    return qu->front ? 0 : 1;
}

/*
 * 输出链式队列各个结点的值
 */
void display(queue *qu) {
    if(empty(qu)) printf("队列为空！\n");
    node *p = qu->front;
    while(p) {
        printf("%5d", p->info);
        p = p->next;
    }
    printf("\n");
}

/*
 * 取得队首结点值
 */
datatype get(queue *qu) {
    if(empty(qu)) {
        printf("队列为空！\n");
        exit(1);
    }
    return qu->front->info;
}

/*
 * 链式队列的插入操作
 */
void *insert(queue *qu, datatype x) {
    node *p = (node *) malloc(sizeof(node));
    p->info = x;
    p->next = NULL;
    if (empty(qu)) {
        qu->front = qu->rear = p;
    } else {
        qu->rear->next = p;
        qu->rear = p;
    }
    return qu;
}

/*
 * 链式队列的删除操作
 */
void *dele(queue *qu) {
    if(empty(qu)) {
        printf("队列为空！\n");
        return qu;
    }
    node *q = qu->front;
    qu->front = q->next;
    free(q);
}
int main() {
    queue *qu = init();
    insert(qu, 1);
    insert(qu, 2);
    insert(qu, 3);
    printf("%d\n", get(qu));
    dele(qu);
    display(qu);
    return 0;
}