首页 > 其他分享 >头歌-01线性表

头歌-01线性表

时间：2023-09-25 09:26:26浏览次数：35  
标签：slist 01 return 线性表 结点 len llist 头歌 curr

第一题 

/*************************************************************
    date: April 2017
    copyright: Zhu En
    DO NOT distribute this code without my permission.
**************************************************************/
// 顺序表操作实现文件
//////////////////////////////////////////////////////////////
#include <stdio.h>
#include <stdlib.h>
#include "Seqlist.h"

SeqList* SL_Create(int maxlen)
// 创建一个顺序表。
// 与SqLst_Free()配对。
{
	SeqList* slist=(SeqList*)malloc(sizeof(SeqList));
	slist->data = (T*)malloc(sizeof(T)*maxlen);
	slist->max=maxlen;
	slist->len=0;
	return slist;
}

void SL_Free(SeqList* slist)
// 释放/删除 顺序表。
// 与SqLst_Create()配对。
{
	free(slist->data);
	free(slist);
}

void SL_MakeEmpty(SeqList* slist)
// 置为空表。
{
	slist->len=0;
}

int SL_Length(SeqList* slist)
// 获取长度。
{
	return slist->len;
}

bool SL_IsEmpty(SeqList* slist)
// 判断顺序表是否空。
{
	return 0==slist->len;
}

bool SL_IsFull(SeqList* slist)
// 判断顺序表是否满。
{
	return slist->len==slist->max;
}

T SL_GetAt(SeqList* slist, int i)
// 获取顺序表slist的第i号结点数据。
// 返回第i号结点的值。
{
	if(i<0||i>=slist->len) {
		printf("SL_GetAt(): location error when reading elements of the slist!\n");		
		SL_Free(slist);
		exit(0);
	}
	else 
		return slist->data[i];
}

void SL_SetAt(SeqList* slist, int i, T x)
// 设置第i号结点的值（对第i号结点的数据进行写）。
{
	if(i<0||i>=slist->len) {
		printf("SL_SetAt(): location error when setting elements of the slist!\n");		
		SL_Free(slist);
		exit(0);
	}
	else 
		slist->data[i]=x;
}

bool SL_InsAt(SeqList* slist, int i, T x)
// 在顺序表的位置i插入结点x, 插入d[i]之前。
// i 的有效范围[0,plist->len]。
{
    // 请在下面的Begin-End之间补充代码，插入结点。
    /********** Begin *********/
    int j;
	if((i<0)||(i>slist->len))  return false;
	if(slist->len==slist->max)  return false;
	for(j=i+1;j<slist->len;j++)
	slist[j]=slist[j-1];
	slist->data[i]=x;
	slist->len++;
	return true;

    /********** End **********/
}

T SL_DelAt(SeqList* slist, int i)
// 删除顺序表plist的第i号结点。
// i的有效范围应在[0,plist->len)内，否则会产生异常或错误。
// 返回被删除的数据元素的值。
{
    // 在下面的Begin-End之间补充代码，删除第i号结点。
    /********** Begin *********/
int j;
	if((i<0)||(i>slist->len))  return false;
	T t=slist->data[i];
	for(j=i;j<slist->len-1;j++)
	slist->data[j]=slist->data[j+1];
	slist->len--;
	return t;
    /********** End **********/
}

int SL_FindValue(SeqList* slist, T x)
// 在顺序表表中查找第一个值为x的结点，返回结点的编号。
// 返回值大于等于0时表示找到值为x的结点的编号，-1表示没有找到。
{
	int i=0;
	while(i<slist->len && slist->data[i]!=x) i++;
	if (i<slist->len) return i;
	else return -1;
}

int SL_DelValue(SeqList* slist, T x)
// 删除第一个值为x的结点。
// 存在值为x的结点则返回结点编号, 未找到返回－1。
{
    // 在下面的Begin-End之间补充代码，删除第一个值为 x 的结点。
    /********** Begin *********/
    int j=SL_FindValue(slist,x);
	if(j!=-1)
	{
		SL_DelAt(slist,j);
	}
	return j;


    /********** End **********/
}

void SL_Print(SeqList* slist)
// 打印整个顺序表。
{
	if (slist->len==0) {
		printf("The slist is empty.\n");		
		return;
	}

	//printf("The slist contains: ");
	for (int i=0; i<slist->len; i++) {
		printf("%d  ", slist->data[i]);
	}

	printf("\n");	
	
}

 

 

第二题 
 /*************************************************************
    date: April 2017
    copyright: Zhu En
    DO NOT distribute this code without my permission.
**************************************************************/
// 单链表实现文件

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

// 1）
LinkList* LL_Create()
// 创建一个链接存储的线性表，初始为空表，返回llist指针。
{
    LinkList* llist=(LinkList*)malloc(sizeof(LinkList));
    llist->front=NULL;
    llist->rear=NULL;
    llist->pre=NULL;
    llist->curr=NULL;
    llist->position=0;
    llist->len=0;
    return llist;
}

// 2）	
void LL_Free(LinkList* llist)
// 释放链表的结点，然后释放llist所指向的结构。
{
    LinkNode* node=llist->front;
    LinkNode* nextnode;
    while(node){
        nextnode=node->next;
        free(node);
        node=nextnode;
    }
    free(llist);
}

// 3）	
void LL_MakeEmpty(LinkList* llist)
// 将当前线性表变为一个空表，因此需要释放所有结点。
{
    LinkNode* node=llist->front;
    LinkNode* nextnode;
    while(node){
        nextnode=node->next;
        free(node);
        node=nextnode;
    }
    llist->front=NULL;
    llist->rear=NULL;
    llist->pre=NULL;
    llist->curr=NULL;
    llist->position=0;
    llist->len=0;
}

// 4）	
int LL_Length(LinkList* llist)
// 返回线性表的当前长度。
{
    return llist->len;
}

// 5）	
bool LL_IsEmpty(LinkList* llist)
// 若当前线性表是空表，则返回true，否则返回 False。
{
    return llist->len==0;
}

// 6）  
bool LL_SetPosition(LinkList* llist, int i)
// 设置线性表的当前位置为i号位置。
// 设置成功，则返回true，否则返回false（线性表为空，或i不在有效的返回）。
// 假设线性表当前长度为len，那么i的有效范围为[0,len]。
{	
    int k;
    /* 若链表为空，则返回*/
    if (llist->len==0) return false;

    /*若位置越界*/
    if( i < 0 || i > llist->len)
    {	printf("LL_SetPosition(): position error");
        return false;
    }

    /* 寻找对应结点*/
    llist->curr = llist->front;
    llist->pre = NULL;
    llist->position = 0;
    for ( k = 0; k < i; k++)	{
        llist->position++;
        llist->pre = llist->curr;
        llist->curr = (llist->curr)->next;
    }
    
    
    return true;
}

// 7)	
int LL_GetPosition(LinkList* llist)
// 获取线性表的当前位置结点的编号。
{
    return llist->position;
}

// 8）	
bool LL_NextPosition(LinkList* llist)
// 设置线性表的当前位置的下一个位置为当前位置。
// 设置成功，则返回true，否则返回false（线性表为空，或当前位置为表尾）。
{
    if (llist->position >= 0 && llist->position < llist->len)
    /* 若当前结点存在，则将其后继结点设置为当前结点*/
    {
        llist->position++;
        llist->pre = llist->curr;
        llist->curr = llist->curr->next;
        return true;
    }
    else 
        return false;
}

// 9）	
T LL_GetAt(LinkList* llist)
// 返回线性表的当前位置的数据元素的值。
{
    if(llist->curr==NULL)
    {
        printf("LL_GetAt(): Empty list, or End of the List.\n");
        LL_Free(llist);
        exit(1);
	}
    return llist->curr->data;
}

// 10）	
void LL_SetAt(LinkList* llist, T x)
// 将线性表的当前位置的数据元素的值修改为x。
{
    if(llist->curr==NULL)
    {
        printf("LL_SetAt(): Empty list, or End of the List.\n");
        LL_Free(llist);
        exit(1);
    }
    llist->curr->data=x;
}

// 11）	
bool LL_InsAt(LinkList* llist, T x)
// 在线性表的当前位置之前插入数据元素x。当前位置指针指向新数据元素结点。
// 若插入失败，返回false，否则返回true。
{	
    LinkNode *newNode=(LinkNode*)malloc(sizeof(LinkNode));
    if (newNode==NULL) return false;

    newNode->data=x;

    if (llist->len==0){
        /* 在空表中插入*/
        newNode->next=NULL;
        llist->front = llist->rear = newNode;
	}
    //当前位置为表头。
    else if (llist->pre==NULL)
    {
        /* 在表头结点处插入*/
        newNode->next = llist->front;
        llist->front = newNode;
    }
    else {  
        /* 在链表的中间位置或表尾后的位置插入*/
        newNode->next = llist->curr;
        llist->pre->next=newNode;
    }
    //插入在表尾后。
    if (llist->pre==llist->rear)
        llist->rear=newNode;
    /* 增加链表的大小*/
    llist->len++;
    /* 新插入的结点为当前结点*/
    llist->curr = newNode;
    return true;
}

// 12）	
bool LL_InsAfter(LinkList* llist, T x)
// 在线性表的当前位置之后插入数据元素x。空表允许插入。当前位置指针将指向新结点。
// 若插入失败，返回false，否则返回true。
{
    // 请在Begin-End之间补充代码，实现结点插入。
    /********** Begin *********/
    LinkNode * newNode=(LinkNode*)malloc(sizeof(LinkNode));
    if(newNode==NULL) return false;
    newNode->data=x;
    if(llist->len==0)
    {
    //在空表插入
        newNode->next=NULL;
        llist->front=llist->rear=newNode;
    }
    else if(llist->curr==llist->rear)
    {
        //在尾结点插入
        newNode->next=NULL;
        llist->rear->next=newNode;
        llist->pre=llist->rear;
        llist->rear=newNode;
        llist->position=llist->len;
    }
    else
    {   
        //在中间插入
        newNode->next=llist->curr->next;
        llist->curr->next=newNode;
        llist->pre=llist->curr;
        llist->position++;
 
    }
    llist->len++;//增加链表的长度
    llist->curr=newNode;
    return true;

    /********** End **********/
}

// 13）	
bool LL_DelAt(LinkList* llist)
// 删除线性表的当前位置的数据元素结点。
// 若删除失败（为空表，或当前位置为尾结点之后），则返回false，否则返回true。
{	
    LinkNode *oldNode;
    /* 若表为空或已到表尾之后，则给出错误提示并返回*/
    if (llist->curr==NULL)
    {	
        printf("LL_DelAt(): delete a node that does not exist.\n");
        return false;
    }
    oldNode=llist->curr;
    /* 删除的是表头结点*/
    if (llist->pre==NULL)
    {	
        llist->front = oldNode->next;
    }
    /* 删除的是表中或表尾结点*/
    else if(llist->curr!=NULL){
        llist->pre->next = oldNode->next;
    }
    if (oldNode == llist->rear)	{
        /* 删除的是表尾结点，则修改表尾指针和当前结点位置值*/
        llist->rear = llist->pre;
    }

    /* 后继结点作为新的当前结点*/
    llist->curr = oldNode->next;

    /* 释放原当前结点*/
    free(oldNode);

    /* 链表大小减*/
    llist->len --;
    return true;
}

// 14）	
bool LL_DelAfter(LinkList* llist)
// 删除线性表的当前位置的后面那个数据元素。
// 若删除失败（为空表，或当前位置时表尾），则返回false，否则返回true。
{
    LinkNode *oldNode;
    /* 若表为空或已到表尾，则给出错误提示并返回*/
    if (llist->curr==NULL || llist->curr== llist->rear)
    {
        printf("LL_DelAfter():  delete a node that does not exist.\n");
        return false;
    }
    /* 保存被删除结点的指针并从链表中删除该结点*/
    oldNode = llist->curr->next;
    llist->curr->next=oldNode->next;
    
    if (oldNode == llist->rear)
        /* 删除的是表尾结点*/
        llist->rear = llist->curr;
    /* 释放被删除结点*/
    free(oldNode);
    /* 链表大小减*/
    llist->len --;
    return true;
}

// 15）	
int LL_FindValue(LinkList* llist, T x)
// 找到线性表中第一个值为x的数据元素的编号。
// 返回值-1表示没有找到，返回值>=0表示编号。
{
    LinkNode* p=llist->front;
    int idx=0;
    while(p!=NULL && p->data!=x) {
        idx++;
        p = p->next;
    }
    if (idx>=llist->len) return -1;
    else return idx;
}

// 16）	
int LL_DelValue(LinkList* llist, T x)
// 删除第一个值为x的数据元素，返回该数据元素的编号。如果不存在值为x的数据元素，则返回-1。
{
    int idx=LL_FindValue(llist, x);
    if (idx<0) return -1;
    LL_SetPosition(llist, idx);
    LL_DelAt(llist);
    return idx;
}

// 17）	
void LL_Print(LinkList* llist)
// 打印整个线性表。
{
    LinkNode* node=llist->front;
    while (node) {
        printf("%d ", node->data);
        node=node->next;
    }
    printf("\n");
}

标签：slist,01,return,线性表,结点,len,llist,头歌,curr
From： https://www.cnblogs.com/haggard/p/17727130.html

相关文章

  • 头歌-01链表及其使用
    第一题#include"linearList.h"node*insertTail(node*h,node*t){//请在此添加代码，补全函数insertTail/**********Begin*********/if(h==NULL){t->next=NULL;returnt;}node*p=h;while(p->next){......
  • 01_Bootstrap基础组件01
    1什么是Bootstrap？Bootstrap，来自Twitter，是目前很受欢迎的前端框架。Bootstrap是基于HTML、CSS、JavaScript的，它简洁灵活，使Web开发更加快捷。它对HTML、CSS和JavaScript进行了封装，使它们使用起来更方便。我们只需要使用它已经设定好的类，或规则，即可快速应用它提供的功能。......
  • Java连接MSSQL2012数据报TLS10 is not accepted by client preferences [TLS13, TLS12
    这一问题好像是因为Java新版本禁用了些老的加密算法引起的，解决方法为修改java.security文件里的配置信息即可。我用的是Java21，在安装目录 Java\jdk-21\conf\security下找到java.security文件，用记事本打开，搜索TLSv1，大概在752行的位置有如下配置信息：jdk.tls.disabledAlgorithm......
  • 合集：NJPC2017
    太长了不放缺省源了，代码都只有主程序部分，不知道这个风格怎么样。个人认为难度顺序：A<B<C<E<F<H<D<G。A入力フォーム/洛谷/AT对\(L\)和\(|S|\)取较小值，输出前这些位即可，复杂度\(\mathcalO(\min(L,|S|))\)。namespaceLgxTpre{staticconstintMAX=5......
  • 20211301 学习笔记3
    20211301《Unix/Linux系统编程》学习笔记3学习目标总结一下一门程序设计语言有哪些必备的要素和技能？这些要素和技能在shell脚本中是如果呈现出来的？教材知识总结10.1sh脚本定义：sh脚本是一个包含sh语句的文本文件、命令解释程序sh要执行该语句sh：sh是解释程序，逐行......
  • P3514 [POI2011] LIZ-Lollipop
    很神奇的题题意：给你一个由\(0\)和\(1\)组成的序列，给出\(q\)个询问，每次询问是否有原序列是否有总和为\(x\)的子段。考虑递推，但是小答案对大答案的影响不好算。考虑大区间对小区间的影响。设当前区间为\([l,r]\),总和为sum，有\(4\)种情况\(a[l]=2,a[r]=2\);这是无......
  • P1967 [NOIP2013 提高组] 货车运输
    P1967[NOIP2013提高组]货车运输因为可能成环，这样可能导致到达点的最小权值不一，所以用最小生成树的方法重新建图然后我是利用倍增的思想建立从i点开始，到上面点的距离ff和最小权值ww因为最小权值不好直接建立，所以不如最后统一建立最后就是寻找最近公共祖先的模板了一组hack......
  • P5268 [SNOI2017] 一个简单的询问
    一个简单的询问显然这个询问并不简单如果做过莫比乌斯反演入门题problemb就会想到利用容斥将询问拆成四个那么我们现在的问题变成如何求[1,l][1,r]两个区间之间的答案，那么也是直接用莫队即可，只是维护的是两个区间的右端点，和原来的莫队有一些不一样，但是大体相同。#include<......
  • Some Recent Thoughts Wrritten By NiuJiawen-2019141490165
    Recently,manystudentswhoarejunioryeararetakingpartininterviewsforexemptstudents.Somehaveobtainedsatisfactoryoffers,whereas,othersthinkitistoohardtogetawonderfuloffer. Andthereisnodoubtthatthelatterwillbefrustrated......
  • ciscn_2019_c_1 题解
    main函数如下：int__cdeclmain(intargc,constchar**argv,constchar**envp){intv4;//[rsp+Ch][rbp-4h]BYREFinit(argc,argv,envp);puts("EEEEEEEhhiii");puts("EEmmmmmmm......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99