文档章节

Algorithm - <List> Intro - Sequence/Linked

e_s
 e_s
发布于 2017/08/16 11:45
字数 1165
阅读 0
收藏 0

 

Sequence List:

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

#define LISTSIZE 100
#define LIST_INCREMENT 10
#define FAILED -1
#define OK 1

typedef int Status;

typedef struct SqList{
    char *base;
    int length;
    int list_size;
}SqList;

Status Init_SqList(SqList *L){
    if(!((*L).base = (char *)malloc(sizeof(char)*LISTSIZE))) return FAILED;
    (*L).length = 0;
    (*L).list_size = LISTSIZE;
    return OK;
}

Status Insert_Elem(SqList *L, int ip, char e){
    // insert position range: [1,L.length+1]
    if(ip<1 || ip>(*L).length+1) return FAILED;
    // if the list is full, re-allocate memory.
    if((*L).length==(*L).list_size) {
        int new_size = (*L).list_size+LIST_INCREMENT;
        if(!((*L).base = (char *)realloc((*L).base, sizeof(char)*new_size))) return FAILED;
        (*L).list_size=new_size;
    }
    // move the part after 'ip' by one space.
    char *ip_pt;
    ip_pt = &((*L).base[ip-1]);
    char *q;
    for (q=&((*L).base[(*L).length-1]); q>=ip_pt; q--) *(q+1) = *q;
    // insert new value to position 'ip'.
    *ip_pt = e;
    (*L).length++;

    return OK;
}

Status Get_Elem(SqList *L, int location, char *e){
    if(location<0 || location>((*L).length)) return FAILED;
    *e = (*L).base[location-1];
    return OK;
}

Status Locate_Elem(SqList L, char e, int *location){
    if(!L.length) return FAILED;
    int i;
    for (i=0;i<L.length;i++){
        if(L.base[i]==e){*location=i+1; break;}
    }
    return OK;
}

Status Delete_Elem(SqList *L, int ip){
    // valid range for 'ip'
    if (ip<1 || ip>(*L).length) return FAILED;
    char *p;
    p=&((*L).base[ip-1]);
    for (;p<(*L).length-1;p++) *p=*(p+1);
    (*L).length--;
    return OK;
}

Points to remember:

1. Data sturct of Sequenced-List;

    One Pointer - <ElemType *base>: indicates the start of the storage space for one instance of this Data Structure.

    Two Int - <length> & <list_size>:  <length> represents the current number of elements inside this list;    <list_size> represents the current limit of the number of elements can be stuffed in the list. <list_size> is '>=' <length>.

 

2. void *realloc((*L).base, sizeof(char)*(LIST_SIZE+LIST_INCREMENT));

    re-allocate a memory space for the pointer specified as the 1st input parameter. It happens when the current storage space of the Seqenced-List is full, so we need to assign a bigger space for the list instance.

 

3. How to get an 'element'/'element pointer' at a specified location within a SqList.

Status Get_Elem(SqList L, int position, ElemType *e){

if(!L.base) return FAILED;
if(position<1 || position>L.length) return FAILED;

*e = L.base[position-1]; // ---------------------------------- KEY STEP!!
return OK;
}


Status Insert_Elem(SqList *L, int postion, int e){

if(!(*L).base)return FAILED;
if(position<1 || position>(*L).length+1)return FAILED;

ElemType *ptr;
ptr = &((*L).base[(*L).length-1]); // ------------------------ KEY STEP!!
int index;
for(index=(*L).length; index>position-1; index--) *(ptr+1)=*(ptr);

(*L).base[position-1]=e;

return OK;
}

 

LinkedList (single-linked list):

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

#define FAILED -1
#define NON_EXIST -2
#define OK 1

typedef int Status;

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


/** Basic Operation to LinkedList; **/
Status Init_List(LinkedList *L){
    if(!(*L=(LinkedList)malloc(sizeof(LNode)))) return FAILED;
    (*L)->data = -1;
    (*L)->next = NULL;
    return OK;
}

Status Insert_Elem(LinkedList *L, int ip, int e){
    // valid range of 'ip':[1,length+1];//Get_Length(L,&length)
    int length;
    if (!Get_Length((*L),&length)) return FAILED;
    if (ip<1 || ip>length+1) return FAILED;
    // create new node;
    LinkedList new_node;
    if (!Init_List(&new_node)) return FAILED;
    new_node->data = e;
    // insertion;
    LinkedList f_node=*L;
    int i;
    for (i=0; i<ip-1; i++) f_node=f_node->next;
    new_node->next = f_node->next;
    f_node->next = new_node;
    return OK;
}

Status Delete_Elem(LinkedList *L, int ip, int *deleted_e){
    //valid range of 'ip':[1,length]
    int length;
    if (!Get_Length(*L,&length)) return FAILED;
    if (ip<1 || ip>length) return FAILED;
    // delete;
    LinkedList f_node=*L, a_node;
    int i;
    for (i=0; i<ip-1; i++) f_node=f_node->next;
    a_node = f_node->next;
    *deleted_e = a_node->data;
    f_node->next = a_node->next;
    free(a_node);
    return OK;
}

Status Locate_Elem(LinkedList L, int e, int *location){
    int i=0, flag=0;
    while(L->next){
        if(L->next->data==e){flag=1;break;}
        L=L->next;
        i++;
    }
    if (!flag){return NON_EXIST;}
    *location = i+1;
    return OK;
}

Status Get_Elem(LinkedList L, int ip, int *e){
    // valid range for 'ip'
    int length;
    Get_Length(L,&length);
    if (ip<1 || ip>length) return FAILED;

    int i=0;
    while(i<ip){L=L->next;i++;}
    *e=L->data;
    return OK;
}

/** Bubble sort; **/
Status Data_Swap(LinkedList *node_1, LinkedList *node_2){
    int *temp;
    temp = (*node_1)->data;
    (*node_1)->data = (*node_2)->data;
    (*node_2)->data = temp;
    return OK;
}
Status Bubble_Sort(LinkedList *L){
    int length;
    Get_Length(*L,&length);

    int i;
    LinkedList mov_node = (*L)->next;
    for (i=0; i<length; i++){
        while(mov_node->next){
            if(mov_node->data > mov_node->next->data) {
                Data_Swap(&mov_node, &(mov_node->next));
            }
            mov_node = mov_node->next;
        }
        mov_node = (*L)->next;
    }
    return OK;
}

/** Merge Sort; **/
Status Merge(LinkedList *L1, LinkedList *L2){
    LinkedList merge_list;
    Init_List(&merge_list);

    Merge_SortedLists(L1, L2, &merge_list);
    *L1=merge_list;
    printf("merge ");
    Print_List(*L1);
    return OK;
}

Status Halve_List(LinkedList *ori_front, int length, LinkedList *header2){
    LinkedList L2=*ori_front;
    int i=0;
    while(i<(length/2)) {L2=L2->next;i++;}

    (*header2)->next=L2->next;
    LinkedList ptr=*header2;
    while(i<length){ptr=ptr->next;i++;}
    ptr->next=NULL;

    L2->next=NULL;

    return OK;
}

Status Merge_Sort(LinkedList *L){
    LinkedList *header1=L;

	int length; Get_Length(*header1,&length);

    if(length>=2){
        LinkedList header2;
        Init_List(&header2);
        Halve_List(header1,length,&header2);

        Merge_Sort(header1);
        Merge_Sort(&header2);
        Merge(header1,&header2);

    }
    return OK;
}

/** Merge 2 Sorted Lists **/
Status Merge_SortedLists(LinkedList *a, LinkedList *b, LinkedList *c){
    // All input params have been initialized. *a*b are sorted.
    LinkedList pa=(*a)->next,pb=(*b)->next;
    LinkedList pc=*c;
    while(pa && pb){
        if(pa->data > pb->data) {
        	pc->next = pb; pc=pc->next; pb=pb->next;
        }
        else {
        	pc->next = pa; pc=pc->next; pa=pa->next;
        }
    }
    while(pa){pc->next=pa; pc=pc->next;pa=pa->next;}
    while(pb){pc->next=pb; pc=pc->next;pb=pb->next;}

    return OK;
}

/** Extra functions; **/
Status Create_List(LinkedList *L, int num){
    // input original list backwardly.
    LinkedList ptr=*L;
    for (;num>0;num--){
        LinkedList p = (LinkedList)malloc(sizeof(LNode));
        p->next = NULL;
        scanf("%d",&p->data);
        ptr->next = p;
        ptr = ptr->next;
    }
    return OK;
}
Status Get_Length(LinkedList L, int *length){
    *length = 0;
    while(L->next){
        (*length)++;
        L=L->next;
    }
    return OK;
}

void Print_List(LinkedList L){
    printf("list contents: ");
    while(L->next){
        printf("%d ",L->next->data);
        L=L->next;
    }
    printf("\n");
}

Points to remember:

1. Data Structure of LinkedList;

    One Pointer - <next>: point to the next <LinkedList>/<LNode> node.

    One Data - <data>: store the <ElemType> data element.

    # notice that throughout the whole code script, we only used <LinkedList> but not <LNode>, so we have to use (*L)->next instead of (*L).next... still don't know why...

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

 

2. node insertion;

    First, validate the insert position;  -> Then initialize a new node; -> Finally, insert the node;

// validate
if(insert_position<1 || insert_postion>len(*L)) return FAILED;

// init a new node
LinkedList new_node;
Init_Node(&new_node);
new_node->data = input_value;

// insertion
LinkedList ptr = *L;
int i;
for(i=0; i<insert_position-1; i++) ptr=ptr->next;
new_node->next = ptr->next;
ptr->next = new_node;

    similar operation for element deletion;

 

© 著作权归作者所有

e_s

e_s

粉丝 0
博文 58
码字总数 24581
作品 0
澳门
程序员
私信 提问
决战Leetcode: easy part(1-50)

本博客是个人原创的针对leetcode上的problem的解法,所有solution都基本通过了leetcode的官方Judging,个别未通过的例外情况会在相应部分作特别说明。 欢迎互相交流! email: tomqianmaple@...

qq_32690999
2018/01/25
0
0
JavaScript链表

链表 定义 链表和数组很相似,不同的是,链表中的元素在内存中不是连续放置的,链表中的元素实际上是由一组节点构成的,其中每一个节点都是由数据元素和指向下一个数据元素的引用(指针)构成...

SVD
2015/12/05
117
0
决战Leetcode: easy part(51-96)

本博客是个人原创的针对leetcode上的problem的解法,所有solution都基本通过了leetcode的官方Judging,个别未通过的例外情况会在相应部分作特别说明。 欢迎互相交流! email: tomqianmaple@...

qq_32690999
2018/02/09
0
0
成对的交换链表的节点 Swap Nodes in Pairs

问题: Given a linked list, swap every two adjacent nodes and return its head. For example, Given , you should return the list as . Your algorithm should use only constant space......

叶枫啦啦
2017/09/02
5
0
LeetCode Question Difficulty Distribution 问题难度和频率分布

Leetcode问题难度和频率分布表 引用自: https://zephyrusara.blogspot.jp/2014/07/leetcode-question-difficulty.html LeetCode Question Difficulty Distribution : Sheet1......

xidiancoder
2017/09/10
0
0

没有更多内容

加载失败,请刷新页面

加载更多

spring cloud

一、从面试题入手 1.1、什么事微服务 1.2、微服务之间如何独立通讯的 1.3、springCloud和Dubbo有哪些区别 1.通信机制:DUbbo基于RPC远程过程调用;微服务cloud基于http restFUL API 1.4、spr...

榴莲黑芝麻糊
21分钟前
2
0
Executor线程池原理与源码解读

线程池为线程生命周期的开销和资源不足问题提供了解决方 案。通过对多个任务重用线程,线程创建的开销被分摊到了多个任务上。 线程实现方式 Thread、Runnable、Callable //实现Runnable接口的...

小强的进阶之路
昨天
6
0
maven 环境隔离

解决问题 即 在 resource 文件夹下面 ,新增对应的资源配置文件夹,对应 开发,测试,生产的不同的配置内容 <resources> <resource> <directory>src/main/resources.${deplo......

之渊
昨天
8
0
详解箭头函数和普通函数的区别以及箭头函数的注意事项、不适用场景

箭头函数是ES6的API,相信很多人都知道,因为其语法上相对于普通函数更简洁,深受大家的喜爱。就是这种我们日常开发中一直在使用的API,大部分同学却对它的了解程度还是不够深... 普通函数和...

OBKoro1
昨天
7
0
轻量级 HTTP(s) 代理 TinyProxy

CentOS 下安装 TinyProxy yum install -y tinyproxy 启动、停止、重启 # 启动service tinyproxy start# 停止service tinyproxy stop# 重启service tinyproxy restart 相关配置 默认...

Anoyi
昨天
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部