算法与数据结构 - 顺序表/单链表 的操作

1.顺序表

手敲的代码:

#include <stdio.h>
#include <stdlib.h>
typedef struct table{
    int *pBase;
    int length;
    int cnt;
    }Student;
//Student p1;
init_arr(Student *p,int length){
    p->pBase=(int *)malloc(sizeof(int)*length);
    p->length=length;
    p->cnt=0;}
append_arr(Student *p,int val){
    p->pBase[p->cnt]=val;
    p->cnt++;
    }
insert_arr(Student *p,int pos,int val){
    //在第pos位置插入值
    int i;
    for(i=0;i<p->cnt;i++){
        printf("插入前:%d\n",p->pBase[i]);
    }
    for(i=p->cnt-1;i>=pos-1;i--){
        p->pBase[i+1]=p->pBase[i];
    }
    p->pBase[pos-1]=val;
    p->cnt++;
    for(i=0;i<p->cnt;i++){
        printf("插入后:%d\n",p->pBase[i]);
    }
}
delete_arr(Student *p,int pos){
    //删除第pos个位置的值
    int i;
    for(i=pos-1;i<=p->cnt-1;i++){
        p->pBase[i]=p->pBase[i+1];
    }
    p->cnt--;
    for(i=0;i<p->cnt;i++){
        printf("删除后:%d\n",p->pBase[i]);
    }
}

int main()
{
    Student *p1;
    init_arr(&p1,10);
    append_arr(&p1,2);
    append_arr(&p1,3);
    append_arr(&p1,8);
    insert_arr(&p1,2,67);
    delete_arr(&p1,3);
    return 0;
}

顺序表的操作,包括初始化、增加元素、插入元素和删除元素。

结构体Student包含三个成员变量,分别是数组首地址、总长度和有效长度

 

由于顺序表以数组形式存储元素,所以使用数组的表达式(a[0]之类的)很容易完成

算法与数据结构 - 顺序表/单链表 的操作

 

运行结果:

算法与数据结构 - 顺序表/单链表 的操作

 

2.单链表

1.尾插法创建链表(尾插法是顺序插入的,方法是一开始将尾指针指向头指针,每次插入新元素,就将尾指针指向新元素,并设置尾指针的next为NULL)

手敲的代码:

#include <stdio.h>
#include <stdlib.h>
typedef struct NODE{
    int data;
    struct NODE *Next;
}NODE,*PNODE;
PNODE create_list(){
    //尾插法
    int len;
    PNODE pNew;
    PNODE pHead = (PNODE)malloc(sizeof(NODE));
    PNODE pTail=pHead;
    printf("请输入len:\n");
    scanf("%d",&len);
    int i=0,data;
    for(i=0;i<len;i++){
        printf("请输入第%d位的data:\n",i);
        scanf("%d",&data);
        PNODE pNew=(PNODE)malloc(sizeof(NODE));
        pNew->data=data;
        pTail->Next=pNew;
        pTail=pNew;
        pNew->Next=NULL;
    }
    return pHead;}
//删除 delete_list(PNODE p,int pos){ int i; for(i=0;i<pos-1;i++){ p=p->Next; } p->Next=p->Next->Next; }
//插入 insert_list(PNODE p,int pos,int val){ int i; for(i=0;i<pos-1;i++){ p=p->Next; } PNODE pNew; pNew=(PNODE)malloc(sizeof(NODE)); pNew->data=val; pNew->Next=p->Next; p->Next=pNew; }
//遍历 travel_list(PNODE p){ while(p->Next!=NULL){ p=p->Next; printf("值:%d\n",p->data); } } int main() { PNODE pHead; pHead=create_list(); delete_list(pHead,3); insert_list(pHead,4,66); travel_list(pHead); }

结果:

算法与数据结构 - 顺序表/单链表 的操作

 

2.头插法创建链表

因为头插法是逆向插入,且不需要尾指针,全靠头指针插入,使用遍历时会发现元素是反着打印的

头插法的特点是头指针的next设为NULL,之后将头指针next赋给新元素的next,最后头指针的next指向新元素

手敲的代码:

#include <stdio.h>
#include <stdlib.h>
typedef struct NODE{
    int data;
    struct NODE *Next;
}NODE,*PNODE;
PNODE create_list(){
    //头插法
    int len;
    PNODE pNew;
    PNODE pHead = (PNODE)malloc(sizeof(NODE));
    pHead->Next=NULL;
    printf("请输入len:\n");
    scanf("%d",&len);
    int i=0,data;
    for(i=0;i<len;i++){
        printf("请输入第%d位的data:\n",i);
        scanf("%d",&data);
        PNODE pNew=(PNODE)malloc(sizeof(NODE));
        pNew->data=data;
        pNew->Next=pHead->Next;
        pHead->Next=pNew;
    }
    return pHead;}
delete_list(PNODE p,int pos){
    int i;
    for(i=0;i<pos-1;i++){
        p=p->Next;
    }
    p->Next=p->Next->Next;
    }
insert_list(PNODE p,int pos,int val){
    int i;
    for(i=0;i<pos-1;i++){
        p=p->Next;
    }
    PNODE pNew;
    pNew=(PNODE)malloc(sizeof(NODE));
    pNew->data=val;
    pNew->Next=p->Next;
    p->Next=pNew;
}
travel_list(PNODE p){
    while(p->Next!=NULL){
        p=p->Next;
        printf("值:%d\n",p->data);
    }
}
int main()
{   PNODE pHead;
    pHead=create_list();
    delete_list(pHead,3);
    insert_list(pHead,4,66);
    travel_list(pHead);
}

结果:

算法与数据结构 - 顺序表/单链表 的操作

上一篇:剑指offer第56题:删除链表中重复的节点


下一篇:两个有序链表的合并