线型表

线型表的顺序表示和实现

#include<iostream>
#include<stdio.h>
#define LIST_INIT_SIZE 100
#define List_Increament 10 //当容量不够时每次增加的容量大小

using namespace std;

typedef struct SqList{
    int *data;
    int length;
    int listsize;  //线型表的容量
}S;

bool Init(SqList &L){
    L.data = (int *)malloc(LIST_INIT_SIZE * sizeof(int));
    if(!L.data) return false;
    L.length = 0;
    L.listsize = LIST_INIT_SIZE;
    return true;
}

// 在第i+1的位置上插入e
bool Insert(SqList &L , int i , int e){
    if(i < 0 || i > L.length){
        return false;
    }
    if(L.length > L.listsize){
        int *newsize = (int *)realloc(L.data , (L.listsize + List_Increament) * sizeof(int));
        if(!newsize) return false;
        L.data = newsize;
        L.listsize += List_Increament;
    }
    int *q = &(L.data[i]);
    for(int *p = &(L.data[L.length - 1]) ; p >= q ; --p){
        *(p+1) = *p;
    }
    *q = e;
    L.length++;
    return true;
}

// 在i+1 的位置上删除元素，放入e中
bool Delete(SqList &L , int i , int &e){
    if(i < 0 || i >= L.length){
        return false;
    }
    int *p = &(L.data[i]);
    e = L.data[i];
    for(int *q = &(L.data[i]) ; q < &(L.data[L.length-1]) ; ++q){
        *q = *(q+1);
    }
    --L.length;
    return true;
}

//合并线型表L1 和 L2 ，放入 L3中, 假设L1和L2均为降序排列，得到的L3也要降序排列
bool MergeList(SqList &L1 , SqList &L2 , SqList &L3){
    int *p1 = L1.data;
    int *p2 = L2.data;
    L3.length = L1.length + L2.length;
    L3.listsize = L1.listsize + L2.listsize;
    L3.data = (int *)malloc(L3.listsize * sizeof(int));
    int *p3 = L3.data;
    if(!L3.data) return false;
    while(p1 <= (L1.data + L1.length - 1) && p2 <= (L2.data + L2.length - 1)){
        if(*p1 > *p2){
            *p3 = *p1;
            *p3++ , *p1++;
        }
        else {
            *p3 = *p2;
            *p3++ , *p2++;
        }
    }
    while(p1 <= (L1.data + L1.length - 1)){
        *p3 = *p1;
        *p3++ , *p1++;
    }
    while(p2 <= (L2.data + L2.length - 1)){
        *p3 = *p2;
        *p3++ , *p2++;
    }
    return true;
}

int main()
{
    //合并
    SqList L1 , L2 , L3;
    Init(L1);
    Init(L2);
    Init(L3);
    for(int i = 0 ; i<5 ; ++i){
        int a;
        cin>>a;
        Insert(L1 , i , a);
    }
    for(int i = 0 ; i<5 ; ++i){
        int a;
        cin>>a;
        Insert(L2 , i , a);
    }
    MergeList(L1 , L2 , L3);
    for(int i = 0 ; i<L3.length ; ++i){
        cout<<L3.data[i]<<' ';
    }


    //插入、删除
    SqList s;
    Init(s);
    for(int i = 0 ; i<10 ; ++i){
        int a;
        cin>>a;
        Insert(s , i , a);
    }
    for(int i = 0 ; i<10 ; ++i){
        cout<<s.data[i]<<' ';
    }
    cout<<endl;
    Insert(s , 5 , 1000);
    for(int i = 0 ; i<s.length ; ++i){
        cout<<s.data[i]<<' ';
    }
    int e;
    Delete(s , 5 , e);
    Delete(s , 3 , e);
    cout<<endl;
    cout<<e<<endl;
    for(int i = 0 ; i<s.length ; ++i){
        cout<<s.data[i]<<' ';
    }
}

线型表的链式表示和实现

#include<iostream>
#include<stdio.h>
#define LIST_INIT_SIZE 100
#define List_Increament 10

using namespace std;

typedef struct LNode {
    int data;
    LNode *next;
}LNode , *LinkList;

//建立一个有n个节点的链表
void CreateList(LinkList &L , int n){
    L = (LinkList)malloc(sizeof(LNode));
    L->next = NULL;
    for(int i = 0 ; i<n ; ++i){
        LinkList p = (LinkList)malloc(sizeof(LNode));
        cin>>p->data;
        p->next = L->next;  // 头插法
        L->next = p;
    }
}

//在第i个位置之前插入 e
bool Insert(LinkList &L , int i , int e){
    LinkList p = L;
    for(int j = 0 ; j<i-1 ; ++j){
        if(p == NULL) return false;
        p = p->next;
    }
    LinkList q = (LinkList)malloc(sizeof(LNode));
    q->data = e;
    q->next = p->next;
    p->next = q;
    return true;
}

//删除第i个节点
bool Delete(LinkList &L , int i , int &e){
    LinkList p = L;
    for(int j = 0 ; j<i-1 ; ++j){
        if(!p) return false;
        p = p->next;
    }
    LinkList q = p->next;
    e = p->next->data;
    p->next = p->next->next;
    free(q);
    return true;
}

void print(LinkList L){
    LinkList p = L->next;
    while(p){
        cout<<p->data<<' ';
        p = p->next;
    }
    cout<<endl;
}

// L1和L2中均为降序排列，合并后的L3中的也为降序
void MergeList(LinkList &L1 , LinkList &L2 , LinkList &L3){
    LinkList p1 = L1->next , p2 = L2->next;
    LinkList p3 = L3 = L1; // 将L1的头结点作为L3的头结点
    while(p1 && p2){
        if(p1->data > p2->data){
            p3->next = p1;
            p3 = p3->next;
            p1 = p1->next;
        }
        else {
            p3->next = p2;
            p3 = p3->next;
            p2 = p2->next;
        }
    }
    p3->next = p1 ? p1 : p2;
    free(L2);
}

int main()
{
    LinkList L1 , L2 , L3;
    int n;
    cin>>n;
    CreateList(L1 , n);
    CreateList(L2 , n);
    print(L1);
    print(L2);
    MergeList(L1 , L2 , L3);
    print(L3);
}

单向循环链表

//没什么不一样的，就变了L->next = L; 而且其他函数的终止条件不可以是p->next == NULL，而是是否等于头指针
void CreateList(LinkList &L , int n){
    L = (LinkList)malloc(sizeof(LNode));
    L->next = L;
    for(int i = 0 ; i<n ; ++i){
        LinkList p = (LinkList)malloc(sizeof(LNode));
        cin>>p->data;
        p->next = L->next;
        L->next = p;
    }
}

循环双向链表

#include<iostream>
#include<stdio.h>
#define LIST_INIT_SIZE 100
#define List_Increament 10

using namespace std;

typedef struct DuLNode {
    int data;
    DuLNode *prior;
    DuLNode *next;
}DuLNode , *DuLinkList;

void CreateList(DuLinkList &L , int n){
    L = (DuLinkList)malloc(sizeof(DuLNode));
    L->next = L;
    L->prior = L;
    for(int i = 0 ; i<n ; ++i){
        DuLinkList p = (DuLinkList)malloc(sizeof(DuLNode));
        cin>>p->data;
        p->next = L->next;
        L->next->prior = p;
        p->prior = L;
        L->next = p;
    }
}

// 在i位置之前插入e
void Insert(DuLinkList &L , int i , int e){
    DuLinkList q = L;
    DuLinkList p = (DuLinkList)malloc(sizeof(DuLNode));
    p->data = e;
    for(int j = 0 ; j<i - 1 ; ++j){
        q = q->next;
    }
    p->next = q->next;
    q->next->prior = p;
    p->prior = q;
    q->next = p;
}

// 删除i位置的结点
void Delete(DuLinkList &L , int i , int &e){
    DuLinkList p = L;
    for(int j = 0 ; j<i ; ++j){
        p = p->next;
    }
    e = p->data;
    p->next->prior = p->prior;
    p->prior->next = p->next;
    free(p);
}

void print(DuLinkList L){
    DuLinkList p = L->next;
    while(p != L){
        cout<<p->data<<' ';
        p = p->next;
    }
    cout<<endl;
    p = p->prior;
    while(p != L){
        cout<<p->data<<' ';
        p = p->prior;
    }
    cout<<endl;
}
int main()
{
    DuLinkList L;
    int n;
    cin>>n;
    CreateList(L , n);
    print(L);
    int e;
    cin>>e;
    Insert(L , 3 , e);
    print(L);
    Delete(L , 2 , e);
    print(L);
    cout<<e;
}