数据结构与算法(三)
发布日期:2021-05-09 09:32:20 浏览次数:3 分类:博客文章

本文共 10717 字,大约阅读时间需要 35 分钟。

双向链表

链表由单向的链变成双向链,使用这种数据结构,我们不再拘束于单链表的单向创建于遍历等操作。

在单链表中,有一个数据域,还有一个指针域,数据域用来存储相关数据,而指针域负责链表之间的“联系”。在双向链表中,需要有两个指针域,一个负责向后连接,一个负责向前连接

//单链表的结构struct List{    int data;	//数据域    struct List *next;	//指针域};//双向链表的结构typedef struct List{    int data;		//数据域    struct List *next;	//向后的指针    struct Lsit *front;		//向前的指针};typedef struct List* pElem;typedef struct List eElem;

同单链表一样,对双向链表的操作也有创建,插入,遍历,删除,销毁。

双向链表的创建

在创建双向链表的时候,需要初始化两个指针。同单链表一样,需要一个头指针来标志链表的信息。可以写出该函数的定义:

pElem CreateList(){    pElem head = (pElem)malloc( sizeof(eElem) );    assert(head != NULL );		//包含于标准库
head -> next = head -> front = NULL; //初始化链表,指针置空 return head;}

双向链表的插入

在单向链表的头插法中,最主要的语句就是tmp->next = head->next,而在双向链表中,多了一个向前的指针。

void InsertElem( pElem head, int data ){    if ( head == NULL ){        printf("The list is empty.\n");		//头结点为空,无法插入        return;    }        pElem tmpHead = head;	//创建一个临时的头结点指针    if( tmpHead->next ==NULL ){        //当双向链表只有一个头结点时		pElem addition = (pElem)malloc( sizeof(eElem) );		assert( addition != NULL );		addition->data = data;		//数据域赋值		addition->next = tmpHead->next;	//后向指针连接		tmpHead->next = addition;		addition->front = tmpHead;		//将插入结点的front指向头结点    }	else{		//当双向链表不只一个头结点时		pElem addition = (pElem)malloc( sizeof(eElem) );		assert( addition != NULL );		addition -> data = data;		//数据域赋值		tmpHead->next->front = addition;		//头结点的下一个结点的front指针		addition->front = tmpHead;		//插入的结点的front指针指向头结点		addition->next = tmpHead->next;		//插入结点的next 指针指向原本头指针的下个结点		tmpHead->next = addition;		//将头结点的next指针指向插入结点	}}

创建一个新的结点addition,此时表中只有头结点,因此执行if中的程序,执行完毕后就变成了:

双向链表的遍历

在遍历中将实现next的向后遍历,也会实现front的向前遍历

void IlluList( pElem head ){	printf("-----------------------------\n");	if( head == NULL ){		printf("The list is empty.\n");		return;	}		pElem tmpHead = head;	while( tmpHead->next != NULL ){		tmpHead = tmpHead->next;	//头结点数据为空,因此直接从头结点的下一结点开始遍历		printf("%d\n", tmpHead->data);	}	//此时tmpHead的地址在链表的最后一个结点处	while( tmpHead->front->front != NULL ){		printf("%d\n", tmpHead->data);		//最后一个结点要输出		tmpHead = tmpHead->front;	}	printf("%d\n", tmpHead->data);	return;}

当向后遍历完成之后,此时tmpHead的地址是链表的最后一个结点的地址,因此使用front来进行向前的遍历,如果判断条件是tmpHead->front !=NULL的话,会将头结点的数据域也输出,然而头结点的数据域未使用,因此会输出一个不确定的值。正因此判断条件改为tmpHead->front->front !=NULL

删除一个结点

当删除一个结点的时候,我们要判断在链表中是否存在与之匹配的结点,有的话删除成功,否则失败。

就像这幅图一样,当删除addition结点时,先讲addition的下一个结点与head相连,而下一个结点是NULL,因此可以得出函数为:

void DeleteElem( pElem head, int data ){	if( head == NULL ){		printf("The list is empty.\n");		return;	}	pElem tmpHead = head;	while( tmpHead->next != NULL ){		tmpHead = tmpHead->next;		if( tmpHead->data == data ){			tmpHead->front->next = tmpHead->next;	//将被删结点的上一个结点的next指针指向被删结点的下一个结点			tmpHead->next->front = tmpHead->front;	//将被删结点的下一个结点front指针指向被删结点的上一个结点			break;		}	}	free(tmpHead);		//释放内存}

销毁链表

销毁一个双向链表的操作同单链表的相似。指针不断向后运动,每运动一个结点,释放上一个结点。

void DestroyList( pElem head ){    pElem tmp;    while( head->next != NULL ){        tmp = head;		//指针不断后移        head = head->next;        free(tmp);    }    free(head);}

此时,tmp的地址就是head的地址,但当执行一个之后,就变成这样。

上一次执行完之后,头结点已经被释放,此时头结点就在第一个数据结点处。以此往后,最后循环结束,释放最后一个结点。

课堂演示题目

要求实现用户输入一个数使得26个字母的排列发生变化,例如用户输入3,输出结果:

  • DEFGHIJKLMNOPQRSTUVWXYZABC

同时需要支持负数,例如用户输入-3,输出结构:

  • XYZABCDEFGHIJKLMNOPQRSTUVW

    #include 
    #include
    #define OK 1#define ERROR 0typedef char ElemType;typedef int Status;typedef struct DualNode{ ElemType data; struct DualNode *prior; struct DualNode *next;}DualNode, *DuLinkList;Status InitList(DuLinkList *L){ DualNode *p, *q; int i; *L = (DuLinkList)malloc(sizeof(DualNode)); if( !(*L) ) { return ERROR; } (*L)->next = (*L)->prior = NULL; p = (*L); for( i=0; i < 26; i++ ) { q = (DualNode *)malloc(sizeof(DualNode)); if( !q ) { return ERROR; } q -> data = 'A'+i; q -> prior = p; q -> next = p -> next; p -> next = q; p = q; } p->next = (*L)->next; (*L)->next->prior = p; return OK;}void Caesar(DuLinkList *L, int i){ if( i > 0 ) { do { (*L) = (*L)->next; }while( --i ); } if( i < 0 ) { do { (*L) = (*L)->next; }while( ++i ); }}int main(){ DuLinkList L; int i, n; InitList(&L); printf("请输入一个整数:"); scanf("%d", &n); printf("\n"); Caesar(&L, n); for( i=0; i < 26; i++ ) { L = L->next; printf("%c", L->data); } printf("\n"); return 0;}

栈和队列

栈:(Stack)是一个后进先出(Last in first out ,LIFO)的线性表,它要求只在表尾进行删除和插入操作。

对于栈来说,表尾称为栈的栈顶(top),相应的表头称为栈底(bottom)。

栈的顺序存储结构

typedef struct{    ElemType *base;    ElemType *top;    int stackSize;}sqStack;

base是指向栈底的指针变量,top是指向栈顶的指针变量,stackSize指示栈的当前可使用的最大容量。

创建一个栈

#define STACK_INIT_SIZE 100initStack(sqStack *s){    s -> base = (ElemType *)malloc(STACK_INIT_SIZE * sizeof(ElemType) );    if( !s->base )        exit(0);    s -> top = s -> base;	//最开始,栈顶就是栈底    s -> stackSize = STACK_INIT_SIZE;}

入栈操作

  • 入栈操作也叫压栈操作,就是向栈中存放数据
  • 入栈操作要在栈顶进行,每次向栈中压入一个数据,top指针就要+1,直到栈满为止。
#define STACKINCREMENT 10Push(sqStack *s, ElemType e){    //如果栈满,追加空间    if( s->top - s->base >= s->stackSize )    {        s->base = (ElemType *)realloc(s->base, (s->stackSize + STACKINCREMENT) * sizeof(ElemType));        if( !s->base )            exit(0);                s->top = s->base + s->stackSize;		//设置栈顶        s->stackSize = s->stackSize + STACKINCREMENT;	//设置栈的最大容量    }           *(s->top) = e;    s->top++;}

出栈操作

  • 出栈操作就是在栈顶取出数据,栈顶指针随之下移的操作

  • 每当从栈内弹出一个数据,栈的当前容量就-1

    Pop(sqStack *s, ElemType *e){    if( s->top == s->base )	//栈已空        return;    *e = *--(s->top);}

清空一个栈

  • 将栈中的元素全部作废,栈本身的物理空间并不发生改变。

  • 只要将s->top的内容赋值为s->base即可,这样s->base等于s->top,也就表明这个栈是空的。

    ClearStack(sqStack *s){    s->top = s->base;}

销毁一个栈

  • 销毁一个栈与清空一个栈不同,销毁一个栈是要释放掉该栈所占据的物理内存空间。

    DestroyStack(sqStack *s){    int i, len;    len = s->stackSize;    for( i=0; i < len; i++ ){        free( s->base );        s->base++;    }    s->base = s->top = NULL;    s->stackSize = 0;}

计算栈的当前容量

  • 计算栈的当前容量也就是计算栈中元素的个数,因此只要返回s.top - s.base即可

  • 注:栈的最大容量是指该栈占据内存空间的大小,其值时s.stackSize, 它与栈的当前容量不是一个概念。

    int StackLen(sqStack s){    return (s.top - s.base );}

实例分析

  • 题目:利用栈的数据结构特点,将二进制转换为十进制数。

    #include 
    #include
    #include
    #define STACK_INIT_SIZE 20#define STACKINCREMENT 10typedef char ElemType;typedef struct{ ElemType *base; ElemType *top; int stackSize;}sqStack;void InitStack(sqStack *s){ s->base = (ElemType *)malloc(STACK_INIT_SIZE * sizeof(ElemType)); if( !s->base ) { exit(0); } s->top = s->base; s->stackSize = STACK_INIT_SIZE;}void Push(sqStack *s, ElemType e){ if( s->top - s->base >= s->stackSize ) { s->base = (ElemType *)realloc(s->base, (s->stackSize + STACKINCREMENT) * sizeof(ElemType) ); if( !s->base ) { exit(0); } } *(s->top) = e; s->top++;}void Pop(sqStack *s, ElemType *e){ if( s->top == s->base ) { return; } *e = *--(s->top);}int StackLen(sqStack s){ return (s.top - s.base);}int main(){ ElemType c; sqStack s; int len, i, sum = 0; InitStack(&s); printf("请输入二进制数,输入#符号表示结束!\n"); scanf("%c", &c); while( c != '#' ) { Push(&s, c); scanf("%c", &c); } getchar(); //把'\n'从缓冲区去掉 len = StackLen(s); printf("栈的当前容量是:%d\n", len); for(i = 0; i < len; i++ ) { Pop(&s, &c); sum = sum + (c-48) * pow(2, i); } printf("转化为十进制数是:%d\n", sum); return 0;}

栈的链式存储结构

  • 栈因为只是栈顶来做插入和删除操作,所以比较好的方法就是将栈顶放在单链表的头部,栈顶指针和单链表的头指针合二为一。

进栈操作

对于栈链的Push操作,假设元素值为e的新结点是s,top为栈顶指针

Status Push(LinkStack *s, ElemType e){    LinkStackPtr p = (LinkStackPtr) malloc (sizeof(StackNode));    p->data = e;    p->next = s->top;    s->top = p;    s->count++;    return OK;}

出栈操作

假设变量p用来存储要删除的栈顶结点,将栈顶指针下移一位,最后释放p即可

Status Pop(LinkStack *s, ElemType *e ){    LinkStackPtr p;    if( StackEmpty(*s))		//判断是否为空栈        return ERROR;    *e = s->top->data;    p = s->top;    s->top = s->top->next;    free(p);    s->count--;    return OK;}

(重点)逆波兰计算器

  • 实现对逆波兰输入的表达式进行计算
  • 支持带小数点的数据
  • 正常表达式----------->逆波兰表达式
    • a+b-------------->a b +
    • a+(b-c) --------------------> a b c - +
    • a+(b-c)*d --------------------> a b c - d * +
    • a+d*(b-c)-----------------> a d b c - * +
#include 
#include
#include
#define STACK_INIT_SIZE 20#define STACKINCREMENT 10#define MAXBUFFER 10typedef double ElemType;typedef struct{ ElemType *base; ElemType *top; int stackSize;}sqStack;InitStack(sqStack *s){ s->base = (ElemType *)malloc(STACK_INIT_SIZE * sizeof(ElemType)); if( !s->base ) exit(0); s->top = s->base; s->stackSize = STACK_INIT_SIZE;}Push(sqStack *s, ElemType e){ // 栈满,追加空间,鱼油必须懂! if( s->top - s->base >= s->stackSize ) { s->base = (ElemType *)realloc(s->base, (s->stackSize + STACKINCREMENT) * sizeof(ElemType)); if( !s->base ) exit(0); s->top = s->base + s->stackSize; s->stackSize = s->stackSize + STACKINCREMENT; } *(s->top) = e; // 存放数据 s->top++;}Pop(sqStack *s, ElemType *e){ if( s->top == s->base ) return; *e = *--(s->top); // 将栈顶元素弹出并修改栈顶指针}int StackLen(sqStack s){ return (s.top - s.base);}int main(){ sqStack s; char c; double d, e; char str[MAXBUFFER]; int i = 0; InitStack( &s ); printf("请按逆波兰表达式输入待计算数据,数据与运算符之间用空格隔开,以#作为结束标志: \n"); scanf("%c", &c); while( c != '#' ) { while( isdigit(c) || c=='.' ) // 用于过滤数字 { str[i++] = c; str[i] = '\0'; if( i >= 10 ) { printf("出错:输入的单个数据过大!\n"); return -1; } scanf("%c", &c); if( c == ' ' ) { d = atof(str); Push(&s, d); i = 0; break; } } switch( c ) { case '+': Pop(&s, &e); Pop(&s, &d); Push(&s, d+e); break; case '-': Pop(&s, &e); Pop(&s, &d); Push(&s, d-e); break; case '*': Pop(&s, &e); Pop(&s, &d); Push(&s, d*e); break; case '/': Pop(&s, &e); Pop(&s, &d); if( e != 0 ) { Push(&s, d/e); } else { printf("\n出错:除数为零!\n"); return -1; } break; } scanf("%c", &c); } Pop(&s, &d); printf("\n最终的计算结果为:%f\n", d); return 0;}

转载地址:https://www.cnblogs.com/zonkidd/p/14412291.html 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:数据结构与算法(四)
下一篇:数据结构与算法(二)

发表评论

最新留言

关注你微信了!
[***.104.42.241]2023年09月09日 18时41分46秒