#include <iostream>
typedef struct line{
    struct line * prior;
    int data;
    struct line * next;
}line;
//双链表的创建
line* initLine(line * head);
//双链表插入元素,add表示插入位置
line * insertLine(line * head,int data,int add);
//双链表删除指定元素
line * delLine(line * head,int data);
//双链表中查找指定元素
int selectElem(line * head,int elem);
//双链表中更改指定位置节点中存储的数据,add表示更改位置
line *amendElem(line * p,int add,int newElem);
//输出双链表的实现函数
void display(line * head);
int main() {
    line * head=NULL;
    //创建双链表
    head=initLine(head);
    display(head);
    //在表中第 3 的位置插入元素 7
    head=insertLine(head, 7, 3);
    display(head);
    //表中删除元素 2
    head=delLine(head, 2);
    display(head);
    printf("元素 3 的位置是:%d\n",selectElem(head,3));
    //表中第 3 个节点中的数据改为存储 6
    head = amendElem(head,3,6);
    display(head);
    return 0;
}
line* initLine(line * head){
    head=(line*)malloc(sizeof(line));
    head->prior=NULL;
    head->next=NULL;
    head->data=1;
    line * list=head;
    for (int i=2; i<=5; i++) {
        line * body=(line*)malloc(sizeof(line));
        body->prior=NULL;
        body->next=NULL;
        body->data=i;
        list->next=body;
        body->prior=list;
        list=list->next;
    }
    return head;
}
line * insertLine(line * head,int data,int add){
    //新建数据域为data的结点
    line * temp=(line*)malloc(sizeof(line));
    temp->data=data;
    temp->prior=NULL;
    temp->next=NULL;
    //插入到链表头,要特殊考虑
    if (add==1) {
        temp->next=head;
        head->prior=temp;
        head=temp;
    }else{
        line * body=head;
        //找到要插入位置的前一个结点
        for (int i=1; i<add-1; i++) {
            body=body->next;
        }
        //判断条件为真,说明插入位置为链表尾
        if (body->next==NULL) {
            body->next=temp;
            temp->prior=body;
        }else{
            body->next->prior=temp;
            temp->next=body->next;
            body->next=temp;
            temp->prior=body;
        }
    }
    return head;
}
line * delLine(line * head,int data){
    line * temp=head;
    //遍历链表
    while (temp) {
        //判断当前结点中数据域和data是否相等,若相等,摘除该结点
        if (temp->data==data) {
            temp->prior->next=temp->next;
            temp->next->prior=temp->prior;
            free(temp);
            return head;
        }
        temp=temp->next;
    }
    printf("链表中无该数据元素");
    return head;
}
//head为原双链表,elem表示被查找元素
int selectElem(line * head,int elem){
//新建一个指针t,初始化为头指针 head
    line * t=head;
    int i=1;
    while (t) {
        if (t->data==elem) {
            return i;
        }
        i++;
        t=t->next;
    }
    //程序执行至此处,表示查找失败
    return -1;
}
//更新函数,其中,add 表示更改结点在双链表中的位置,newElem 为新数据的值
line *amendElem(line * p,int add,int newElem){
    line * temp=p;
    //遍历到被删除结点
    for (int i=1; i<add; i++) {
        temp=temp->next;
    }
    temp->data=newElem;
    return p;
}
//输出链表的功能函数
void display(line * head){
    line * temp=head;
    while (temp) {
        if (temp->next==NULL) {
            printf("%d\n",temp->data);
        }else{
            printf("%d->",temp->data);
        }
        temp=temp->next;
    }
}

#include <iostream>
//节点
typedef struct Link {
    int  elem;
    struct Link *next;
}link;
//初始化链表
link * initLink();
//链表插入的函数,p是链表,elem是插入的结点的数据域,add是插入的位置
link * insertElem(link * p, int elem, int add);
//删除结点的函数,p代表操作链表,add代表删除节点的位置
link * delElem(link * p, int add);
//查找结点的函数,elem为目标结点的数据域的值
int selectElem(link * p, int elem);
//更新结点的函数,newElem为新的数据域的值
link *amendElem(link * p, int add, int newElem);
void display(link *p);
int main() {
    //初始化链表(1,2,3,4)
    printf("初始化链表为:\n");
    link *p = initLink();
    display(p);
    printf("在第4的位置插入元素5:\n");
    p = insertElem(p, 5, 4);
    display(p);
    printf("删除元素3:\n");
    p = delElem(p, 3);
    display(p);
    printf("查找元素2的位置为:\n");
    int address = selectElem(p, 2);
    if (address == -1) {
        printf("没有该元素");
    }
    else {
        printf("元素2的位置为:%d\n", address);
    }
    printf("更改第3的位置上的数据为7:\n");
    p = amendElem(p, 3, 7);
    display(p);
    return 0;
}
link * initLink() {
    link * p = (link*)malloc(sizeof(link));//创建一个头结点
    link * temp = p;//声明一个指针指向头结点,用于遍历链表
    //生成链表
    for (int i = 1; i < 5; i++) {
        link *a = (link*)malloc(sizeof(link));
        a->elem = i;
        a->next = NULL;
        temp->next = a;
        temp = temp->next;
    }
    return p;
}
link * insertElem(link * p, int elem, int add) {
    link * temp = p;//创建临时结点temp
    //首先找到要插入位置的上一个结点
    for (int i = 1; i < add; i++) {
        temp = temp->next;
        if (temp == NULL) {
            printf("插入位置无效\n");
            return p;
        }
    }
    //创建插入结点c
    link * c = (link*)malloc(sizeof(link));
    c->elem = elem;
    //向链表中插入结点
    c->next = temp->next;
    temp->next = c;
    return  p;
}
link * delElem(link * p, int add) {
    link * temp = p;
    //遍历到被删除结点的上一个结点
    for (int i = 1; i < add; i++) {
        temp = temp->next;
        if (temp->next == NULL) {
            printf("没有该结点\n");
            return p;
        }
    }
    link * del = temp->next;//单独设置一个指针指向被删除结点,以防丢失
    temp->next = temp->next->next;//删除某个结点的方法就是更改前一个结点的指针域
    free(del);//手动释放该结点,防止内存泄漏
    return p;
}
int selectElem(link * p, int elem) {
    link * t = p;
    int i = 1;
    while (t->next) {
        t = t->next;
        if (t->elem == elem) {
            return i;
        }
        i++;
    }
    return -1;
}
link *amendElem(link * p, int add, int newElem) {
    link * temp = p;
    temp = temp->next;//tamp指向首元结点
    //temp指向被删除结点
    for (int i = 1; i < add; i++) {
        temp = temp->next;
    }
    temp->elem = newElem;
    return p;
}
void display(link *p) {
    link* temp = p;//将temp指针重新指向头结点
    //只要temp指针指向的结点的next不是Null,就执行输出语句。
    while (temp->next) {
        temp = temp->next;
        printf("%d ", temp->elem);
    }
    printf("\n");
}

顺序表就是申请连续的内存将元素一次存储,存储逻辑关系为“一对一”。

#include <iostream>

//自定义一个顺序表
typedef struct Table{
    int *head;//用来动态保存数组
    int length;//记录顺序表的长度,也就是表中存储数据元素的个数
    int size;//记录顺序表的存储容量
}table;

//初始化一个顺序表:给 head 动态数据申请足够大小的物理空间;给 size 和 length 赋初值;
#define Size 5 //顺序表申请内存的大小
table initTable(){
    table t;
    t.head = (int*)malloc(Size*sizeof(int));//申请空间
    if (!t.head) //如果申请失败,作出提示并直接退出程序
    {
        printf("初始化失败");
        exit(0);
    }
    t.length=0;//空表的长度初始化为0
    t.size=Size;//空表的初始存储空间为Size
    return t;
}

//顺序表插入元素
table addTable(table t,int elem,int add){//插入函数,其中,elem为插入的元素,add为插入到顺序表的位置
    if (add>t.length+1||add<1) {//判断插入本身是否存在问题(如果插入元素位置比整张表的长度+1还大(如果相等,是尾随的情况),或者插入的位置本身不存在,程序作为提示并自动退出)
        printf("插入位置有问题\n");
        return t;
    }
    //做插入操作时,首先需要看顺序表是否有多余的存储空间提供给插入的元素,如果没有,需要申请
    if (t.length==t.size) {
        t.head=(int *)realloc(t.head, (t.size+1)*sizeof(int));//realloc(void *ptr,size_t size);realloc是在已经分配好内存块的重新分配,如果开始指针分配为NULL,则和malloc用法一致,否则如果开始内存块小,保存原内存块,再次基础新增,如果是开始内存块大,则在此基础减去尾部内存块。返回值是分配好内存块的头指针。
        if (!t.head) {
            printf("存储分配失败\n");
            return t;
        }
        t.size+=1;
    }
    //插入操作,需要将从插入位置开始的后续元素,逐个后移
    for (int i=t.length-1; i>=add-1; i--) {
        t.head[i+1]=t.head[i];
    }
    //后移完成后,直接将所需插入元素,添加到顺序表的相应位置
    t.head[add-1]=elem;
    //由于添加了元素,所以长度+1
    t.length++;
    return t;
}

//顺序表删除元素
table delTable(table t,int add){
    if (add>t.length || add<1) {
        printf("被删除元素的位置有误\n");
        return t;
    }
    //删除操作
    for (int i=add; i<t.length; i++) {
        t.head[i-1]=t.head[i];
    }
    t.length--;
    return t;
}

//顺序表查找元素
int selectTable(table t,int elem){//查找函数,其中,elem表示要查找的数据元素的值
    for (int i=0; i<t.length; i++) {
        if (t.head[i]==elem) {
            return i+1;
        }
    }
    return -1;//如果查找失败,返回-1
}

//顺序表更改元素
//更改函数,其中,elem为要更改的元素,newElem为新的数据元素
table amendTable(table t,int elem,int newElem){
    int add=selectTable(t, elem);
    t.head[add-1]=newElem;//由于返回的是元素在顺序表中的位置,所以-1就是该元素在数组中的下标
    return t;
}
//输出顺序表中元素的函数
void displayTable(table t){
    for (int i=0;i<t.length;i++) {
        printf("%d ",t.head[i]);
    }
    printf("\n");
}
int main() {
    table t1=initTable();
    for (int i=1; i<=Size; i++) {
        t1.head[i-1]=i;
        t1.length++;
    }
    printf("原顺序表:\n");
    displayTable(t1);

    printf("删除元素1:\n");
    t1=delTable(t1, 1);
    displayTable(t1);

    printf("在第2的位置插入元素5:\n");
    t1=addTable(t1, 5, 2);
    displayTable(t1);

    printf("查找元素3的位置:\n");
    int add=selectTable(t1, 3);
    printf("%d\n",add);

    printf("将元素3改为6:\n");
    t1=amendTable(t1, 3, 6);
    displayTable(t1);
    return 0;
}

几种常见的算法时间复杂度的比较(又小到大):
O(1)常数阶 < O(logn)对数阶 < O(n)线性阶 < O(n2)平方阶 < O(n3)(立方阶) < O(2n) (指数阶)
关于对数

int count = 1;
while(count < n)
{  
 
   count = count*2;
   //时间复杂度O(1)的程序步骤序列
   ......
 
}

由于每次count乘以2之后,就距离n更近了一分。也就是说,有多少个2相乘后大于等于n,则会退出循环。由2^x=n 得到x=logn。所以这个循环的时间复杂度为O(logn).

计算机系统软件体系结构采用一种层的结构,有人说过一句名言: “计算机科学领域的任何问题都可以通过增加一个间接的中间层来解决”遗憾的是,这句经典的名言出处无从考证,据说是有人从图灵奖的获得者Butler Lampson的讲座上听来的;也有人说是EDSAC的发明者David Wheeler讲的;还有人指出这是CMU计算机系创始人Alan Perlis的名言。 “Any problem in computer science can be solved by another layer of indirection.” 这句话几乎概括了计算机系统软件体系结构的设计要点,整个体系结构从上到下都是按照严格的层次结构设计的。不仅是计算机系统软件整个体系是这样的,体系里面的每个组件比如操作系统本身,很多应用程序、软件系统甚至很多硬件结构都是按照这种层次的结构组织和设计的。
--摘自《程序员的自我修养》