首页 > 其他分享 >【DS】源代码共享

【DS】源代码共享

时间：2022-09-27 15:47:51浏览次数：50  
标签：index head temp int next printf 共享 源代码 DS

1、顺序表

//
//  DS01_sqlist.c
//  MacC_Learn01
//
//  Created by Remoo on 2022/9/6.
//
//  Xcode Dev
//

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

#define INITSIZE 10
typedef struct
{
    int *data;
    int length;
    int listsize;
}sqlist;//表头
void initlist(sqlist *L);
int getlen(sqlist *L);
int getelem(sqlist *L,int i, int *e);
void list(sqlist *L);
int insert(sqlist *L,int i,int x);
int SeqListErase(sqlist* sl, int pos);
int main(void)
{
    sqlist sq_list;
    int x;
    int *elem=(int *)malloc(sizeof(int));
    
    initlist(&sq_list);
    //此时sq_list的data已经存储了malloc出来的内存首地址
    printf("input datas(-1:end):");
    scanf("%d",&x);
    int i=1;
    while(x!=-1)
    {
        insert(&sq_list,i,x);                  /* 插入 */
        i++;
        scanf("%d",&x);
    }
    printf("目前顺序表元素如下:\n");
    list(&sq_list);                             /* 输出顺序表 */
    
    int index,x0;
    printf("在第几位序插入什么元素：\n");
    scanf("%d %d",&index,&x0);
    if(insert(&sq_list,index,x0))
        list(&sq_list);
    else
        printf("插入失败!");
    
    
    printf("取第几个元素：\n");
    int n;
    scanf("%d",&n);
    if(getelem(&sq_list,n,elem))
        printf("取出的元素是：%d\n",*elem);
    else
        printf("取出失败!");
    printf("删除第几个元素：\n");
    int d;
    scanf("%d",&d);
    if(SeqListErase(&sq_list,d))
        list(&sq_list);
    else
        printf("删除失败！");
    free(sq_list.data);
    free(elem);
    return 0;
}

/* 1.初始化操作(创建一个空的顺序表L) */
void initlist(sqlist *L)
{
    L->data=(int *)malloc(sizeof(int)*INITSIZE);/* 申请存储空间*/
    L->length=0;              /* 初始长度为0 */
    L->listsize=INITSIZE;     /* 容量为初始量 */
}

/* 2. 求表长操作 */
int getlen(sqlist *L)
{return(L->length);}

/* 3. 取元素操作 */
int getelem(sqlist *L,int i, int *e)
{
    if(i<1||i>L->length) return 0;
    *e = L->data[i-1];
    return 1;
}

/* 4.输出操作(输出顺序表L的各数据元素值) */
void list(sqlist *L)
{
    int i;
    for(i=0;i<L->length;i++)
    printf("%5d ",L->data[i]);
    printf("\n");
}
/* 5. 插入操作(在顺序表L中的第i个位序上插入一个值为x的数据元素) */
int insert(sqlist *L,int i,int x)
{
    int j;
    if(i<1||i>L->length+1) return 0;  // 参数i不合理,返回0 
    if(L->length==L->listsize)        // 存储空间不够，增加一个存储空间 
    {
        L->data=(int *)realloc(L->data,(L->listsize+1)*sizeof(int));
        L->listsize++;                 // 增加一个存储空间长度 
    }
    for(j=L->length-1;j>=i-1;j--)
        L->data[j+1]=L->data[j];        // 将序号为i及之后的数据元素后移一位 
    L->data[i-1]=x;                   // 在序号i处放入x 
    L->length++;                      // 顺序表长度增1 
    return 1;                         // 插入成功,返回1 
}

int SeqListErase(sqlist* sl, int pos){
    if(pos > sl->length)return 0;
    for (int i = pos; i < sl->length; i++){
        sl->data[i - 1] = sl->data[i];
    }
    sl->length--;
    return 1;
}

2、单向链表

 

//
//  DS002_LNode.c
//  DataStructure
//
//  Created by Remoo on 2022/9/17.
//
//  Xcode Dev
//

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

typedef struct LNode{
    int data;
    struct LNode* next;
}lnode;

//基本操作
lnode* CreateLNode(int n);
int GetLinkLength(lnode *head);
int GetValue(lnode *head,int index);
int FindIndex(lnode *head,int value);
int Delete(lnode *head,int index);
int InsertValue(lnode *head,int index,int value);
void PrintLink(lnode *head);

//涉及算法
int Turn(lnode *head);

int main(void){
    int temp=0;int value=0;
    
    printf("输入_初始化元素（10个）:");
    lnode* test=CreateLNode(10);
    printf("%d",test->data);
    PrintLink(test);
    
    printf("元素数量:%d\n",GetLinkLength(test));
    
    Turn(test);
    PrintLink(test);
    
    printf("输入_位序：");
    scanf("%d",&temp);
    value = GetValue(test,temp);
    printf("\n取得值：%d\n",value);

    printf("输入_元素：");
    scanf("%d",&temp);
    value = FindIndex(test,temp);
    printf("\n取得位序：%d\n",value);
    
    printf("输入_待删除位序：");
    scanf("%d",&temp);
    if(Delete(test,temp))printf("\nsucceed");else printf("\nfaild!");
    PrintLink(test);
    
    printf("输入_待插入位序、数值：");
    scanf("%d %d",&temp,&value);
    if(InsertValue(test,temp,value))printf("\nsucceed");else printf("\nfaild!");
    PrintLink(test);
    
}

//创建单链表
lnode *CreateLNode(int n){
    lnode* p_head,*p_next,*p_loop;
    int i;
    p_next=p_head=(lnode*)malloc(sizeof(lnode));
    for (i=1; i<=n; i++) {
        p_loop=(lnode*)malloc(sizeof(lnode));
        scanf("%d",&p_loop->data);
        p_next->next=p_loop;
        p_next=p_loop;
    }
    p_next->next=NULL;
    return p_head;
}
//取得链表长度
int GetLinkLength(lnode *head){
    lnode *p;int n;
    n=0;
    p=head->next;
    while(p!=NULL){
        n++;p=p->next;
    }
    return n;
}
//取得元素值
int GetValue(lnode *head,int index){
    lnode *p;int j;
    if(index<1)return 0;
    j=1;p=head->next;
    while(p!=NULL&&j<index){
        p=p->next;j++;
    }
    if(p==NULL)return 0;
    return p->data;
}
//查找元素索引
int FindIndex(lnode *head,int value){
    int i = 1;
    lnode *p_temp = head->next;
    while(p_temp!=NULL&&p_temp->data!=value){
        p_temp=p_temp->next;i++;
    }
    return i;
}
//删除元素
int Delete(lnode *head,int index){
    lnode *p_1,*p_2;int j;
    if(index<1&&index>GetLinkLength(head))
        return 0;
    p_1=head;j=0;
    while(p_1->next!=NULL&&j<index-1){
        p_1=p_1->next;j++;
    }
    p_2=p_1->next;
    p_1->next=p_2->next;
    free(p_2);
    return 1;
}
//插入元素
int InsertValue(lnode *head,int index,int value){
    lnode *p_1,*p_new;int j;
    if(index<1)return 0;
    p_1=head;j=0;
    while(p_1!=NULL&&j<index-1){
        p_1=p_1->next;j++;
    }
    if(p_1==NULL)return 0;
    p_new=(lnode*)malloc(sizeof(lnode));
    p_new->data=value;
    p_new->next=p_1->next;
    p_1->next=p_new;
    return 1;
}
//打印链表
void PrintLink(lnode *head){
    lnode *p;int index;
    p=head->next;index=1;printf("\n");
    while(p!=NULL){
        printf("%3d:%-3d\t",index,p->data);
        p=p->next;index++;
    }
    printf("\n");
}
//逆置元素
int Turn(lnode *head){
    lnode *p,*q;
    p=head->next;
    head->next=NULL;
    while(p!=NULL){//断头，然后头连屁股。重复。
        q=p->next;
        p->next=head->next;
        head->next=p;
        p=q;
    }
    return 1;
}

3、双链表

 

//
//  DS03_DNode.c
//  DS03_DNode
//
//  Created by Remoo on 2022/9/26.
//
//  Xcode Dev
//

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

typedef struct DNode{
    int data;
    struct DNode *next;//下一个节点 后驱节点
    struct DNode *pr;//上一个节点 前驱节点
}dlink;

//基本操作
dlink* CreateDNode(int n);
int Insert(dlink *head,int index,int value);
int Delete(dlink *head,int index);
void PrintLink(dlink *head);//与LNode一样,只是增加了逆向输出的功能
int GetLinkLength(dlink *head);//与LNode一样
int GetValue(dlink *head,int index);//与LNode一样
int FindIndex(dlink *head,int value);//与LNode一样
//算法1
void Move(dlink *head);


int main() {
    int temp=0;
    dlink* test=CreateDNode(5);
    PrintLink(test);
    Move(test);
    PrintLink(test);
        
    printf("元素数量:%d\n",GetLinkLength(test));

    Insert(test,2,100);
    PrintLink(test);
    
    printf("输入_待删除位序：");
    scanf("%d",&temp);
    if(Delete(test,temp))printf("\nsucceed");else printf("\nfaild!");
    PrintLink(test);
}


//把所有大于等于0的数放在负数的前面
    /*
     分析：现将p赋值为位序1的地址，q赋值为链表尾部地址。
     p从左向右寻找最近的非负数，q从右向左寻找负数，然后两者交换。循环上述操作。
     */
    
void Move(dlink *head){
    dlink *p,*q;int temp;
    p=head->next;
    for (q=head; q->next!=NULL; q=q->next);//直接将q移动到节点的尾部
    while(p!=q){
        while(p!=q&&p->data>=0)p=p->next;
        while(p!=q&&q->data<0)q=q->pr;
        if(p!=q){
            temp=p->data;
            p->data=q->data;
            q->data=temp;
        }
    }
}


//创建双链表
    /*
     分析：双链表的结构与单链表类似，只是多了一个前驱节点。
     */
dlink* CreateDNode(int n){
    dlink *head,*p,*q;int i;
    p=head=(dlink*)malloc(sizeof(dlink));//先给头节点指针、位序1的指针开辟内存空间
    for(i=1;i<=n;i++){
        q=(dlink*)malloc(sizeof(dlink));
        scanf("%d",&q->data);
        q->pr=p;
        p->next=q;
        p=q;
    }
    p->next=head->pr=NULL;//两端节点置空
    return head;
}
//取得链表长度
    /*
     分析：与单链表一致。
     */
int GetLinkLength(dlink *head){
    dlink *p;int n;
    n=0;
    p=head->next;
    while(p!=NULL){
        n++;p=p->next;
    }
    return n;
}
    /*
     分析：与单链表一致。
     */
int GetValue(dlink *head,int index){
    dlink *p;int j;
    if(index<1)return 0;
    j=1;p=head->next;
    while(p!=NULL&&j<index){
        p=p->next;j++;
    }
    if(p==NULL)return 0;
    return p->data;
}
    /*
     分析：与单链表一致。
     */
int FindIndex(dlink *head,int value){
    int i = 1;
    dlink *p_temp = head->next;
    while(p_temp!=NULL&&p_temp->data!=value){
        p_temp=p_temp->next;i++;
    }
    return i;
}
//删除链表
    /*
     分析：先确定删除位置i的合理性，包括输入值要大于等于1且小于链表长度。
     其次将指针定位到需要删除的节点位序上。然后取出前驱节点和后驱节点。
     将上一个节点的next地址赋值给下一个节点的pr，奖下一个节点的pr赋值给上一个节点的next。
     最后free需要删除的节点即可。
     */
int Delete(dlink *head,int index){//index输入的是位序
    dlink *n;int i;
    if(index<1&&index>GetLinkLength(head))return 0;
    n=head;i=0;
    while(n->next!=NULL&&i!=index){
        n=n->next;i++;
    }//现在n已经指到了index的位置了
    n->pr->next=n->next;
    n->next->pr=n->next;
    free(n);
    return 1;
}
//插入元素
    /*
     首先判断输入i合理性，包括输入值要大于等于1且小于链表长度。
     其次将指针n指向位序i。
     创建malloc一个new节点，data赋值对应内容value。
     new节点的后驱节点是原位序为i的地址，new的前驱节点是原位序为i的前驱节点。
     然后将原位序为i的前驱节点的后驱节点改为new的地址，将原位序为i的前驱节点改为new的地址。
     */
int Insert(dlink *head,int index,int value){
    dlink *n,*new;int i;
    if(index<1&&index>GetLinkLength(head))return 0;
    n=head;i=0;
    while(n->next!=NULL&&i!=index){
        n=n->next;i++;
    }//现在n已经指到了index的位置了
    new=(dlink*)malloc(sizeof(dlink));
    new->data=value;
    
    new->next=n;
    new->pr=n->pr;
    n->pr->next=new;//这一行需要小心
    n->pr=new;
    return 1;
}
//打印链表
void PrintLink(dlink *head){
    dlink *p;int index;
    p=head;index=0;printf("\n顺序输出：");
    while(p->next!=NULL){
        p=p->next;index++;
        printf("%3d:%-3d\t",index,p->data);
    }
    printf("\n逆序输出：");
    while(p!=head){
        printf("%3d:%-3d\t",index,p->data);
        p=p->pr;index--;
    }
    printf("\n");
}

4、循环单向链表

//
//  main.c
//  DS04_circleList
//
//  Created by Remoo on 2022/9/27.
//
//  Xcode Dev
//

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

typedef struct CNode{
    int data;
    struct CNode *next;
}cnode;

//基本算法
cnode *CreateList(int n);
int GetLinkLength(cnode *head);
int GetValue(cnode *head,int index);
int FindIndex(cnode *head,int value);
int Delete(cnode *head,int index);
int InsertValue(cnode *head,int index,int value);
void PrintLink(cnode *head);


//创建循环链表
cnode *CreateCNode(int n){
    cnode *head,*p,*s;
    int i;
    p=head=(cnode*)malloc(sizeof(cnode));
    for(i=1;i<=n;i++){
        s=(cnode*)malloc(sizeof(cnode));
        scanf("%d",&s->data);
        p->next=s;
        p=s;
    }
    p->next=head;//尾巴指向头部，即为循环单链表。其余和单链表一致。
    return head;
}
//取得链表长度
int GetLinkLength(cnode *head){
    cnode *p;int n;n=0;
    p=head->next;
    while(p!=head){//只有这一个地方与单链表相异
        n++;p=p->next;
    }
    return n;
}
//取元素操作
int GetValue(cnode *head,int index){
    cnode *p;int j;
    if(index<1)return 0;
    j=1;p=head->next;
    while(p!=head&&j<index){//这里与单链表相异
        p=p->next;j++;
    }
    if(p==head)return 0;//这里与单链表相异
    return p->data;
}
//查找元素索引
int FindIndex(cnode *head,int value){
    int i = 1;
    cnode *p_temp = head->next;
    while(p_temp!=head&&p_temp->data!=value){//这里与单链表相异
        p_temp=p_temp->next;i++;
    }
    return i;
}
//删除元素
int Delete(cnode *head,int index){
    cnode *p_1,*p_2;int j;
    if(index<1&&index>GetLinkLength(head))
        return 0;
    p_1=head;j=0;
    while(p_1->next!=head&&j<index-1){//这里与单链表相异
        p_1=p_1->next;j++;
    }
    p_2=p_1->next;
    p_1->next=p_2->next;
    free(p_2);
    return 1;
}
//插入元素
int InsertValue(cnode *head,int index,int value){
    cnode *p_1,*p_new;int j;
    if(index<1)return 0;
    p_1=head;j=0;
    while(p_1->next!=head&&j<index-1){//这里与单链表相异
        p_1=p_1->next;j++;
    }
    if((p_1->next!=head)||(p_1->next==head&&j==index-1)){//这里与单链表相异
        p_new=(cnode*)malloc(sizeof(cnode));
        p_new->data=value;
        p_new->next=p_1->next;
        p_1->next=p_new;
        return 1;
    }
    else return 0;
}
//打印链表
void PrintLink(cnode *head){
    cnode *p;int index;
    p=head->next;index=1;printf("\n");
    while(p!=head){//这里与单链表相异
        printf("%3d:%-3d\t",index,p->data);
        p=p->next;index++;
    }
    printf("\n");
}

int main() {
    int temp=0;int value=0;
    
    printf("输入_初始化元素（10个）:");
    cnode* test=CreateCNode(10);
    printf("%d",test->data);
    PrintLink(test);
    
    printf("元素数量:%d\n",GetLinkLength(test));

    printf("输入_位序：");
    scanf("%d",&temp);
    value = GetValue(test,temp);
    printf("\n取得值：%d\n",value);

    printf("输入_元素：");
    scanf("%d",&temp);
    value = FindIndex(test,temp);
    printf("\n取得位序：%d\n",value);
    
    printf("输入_待删除位序：");
    scanf("%d",&temp);
    if(Delete(test,temp))printf("\nsucceed");else printf("\nfaild!");
    PrintLink(test);
    
    printf("输入_待插入位序、数值：");
    scanf("%d %d",&temp,&value);
    if(InsertValue(test,temp,value))printf("\nsucceed");else printf("\nfaild!");
    PrintLink(test);
    
}

 

标签：index,head,temp,int,next,printf,共享,源代码,DS
From： https://www.cnblogs.com/remyuu/p/16734773.html

相关文章

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99