24/07/09数据结构(3.1206)数组OJ单链表实现

2024-07-10 07:02:01
开发
7

先做几个练习回顾一下前两个博的顺序表:

1.给定一个排序数组,你需要在原地删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度.不需要使用额外的数组空间,你必须在原地修改数组并使用O(1)额外空间的条件下完成.

给定 nums = [0, 0, 1, 1 ,1, 2, 2, 3, 3, 4],函数应该返回新的长度5,并且原数组 nums 的前5个元素被修改为0, 1, 2, 3, 4

   int removeDuplicates(int* nums, int numSize){
       if (numsSize <= 1)
           return numsSize;
       int i = 0, j = 1, idx = 0;
       while (j < numsSize){
           nums[idx++] = nums[i];

           if (num[i] == nums[j]){
               //找到非重复元素的第一个位置
               while (j < numsSize && nums[i] == nums[j])
                   ++j;

               i = j;
               ++j;
           }
           else{
               ++i;
               ++j;
           }
       }
       if (i < numsSize)
           nums[idx++] = num[i];
       return idx;
   }

2.合并两个有序数组,给你两个有序整数数组nums1和nums2,请你将nums2合并到nums1中,使nums1成为一个有序数组.

说明:初始化nums1和nums2的元素数量分别为 m 和 n.

你可以假设nums1有足够的空间(空间大于或等于 m+n)来保存nums2中的元素

实例:nums1 = [1, 2, 3, 0, 0], m = 3

nums2 = [2, 5, 6], n = 3 输出[1, 2, 2, 3, 5, 6]

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n){
   int* nums3 = (int*)malloc(sizeof(int)* (m + n));
   int i = 0, j = 0, idx = 0;
   //同时遍历
   while (i < m && j < n){
       if (nums1[i] <= nums2[j]){
           nums3[idx++] = nums1[i++];
       }
       else{
           nums3[idx++] = nums2[j++];
       }
   }
   //判断是否有剩余元素
   if (i < m)
       memcpy(nums3 + idx, nums1 + i, sizeof(int)* (m - i));

   if (j < n)
       memcpy(nums3 + idx, nums2 + j, sizeof(int)* (n - j));

memcpy(nums1, nums3, sizeof(int)* (m + n));
free(nums3);
}

换一种方法(插入):

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n){
   int i = m - 1, j = n - 1, idx = m + n - 1;
   while (i >= 0 && j >= 0){
       if (nums1[i] > nums2[j])
           nums1[idx--] = nums1[i--];
       else
           nums1[idx--] = nums2[j--];
   }
   //判断nums2中是否有剩余元素
   if (j >= 0){
       memcpy(nums1, nums2, sizeof(int)* (j + 1));
   }

3.旋转数组给定一个数组,将数组中的元素向右移动k个位置,其中k是非负数

示例: 输入:[1, 2, 3, 4, 5, 6, 7] 和 k = 3

输出:[5, 6, 7, 1, 2, 3, 4]

void reverse(int* num, int start, int end){
   while (start < end){
       int tmp = num[start];
       num[start] = num[end];
       num[end] = tmp;
       ++start;
       --end;
   }
}
void rotate(int* nums, int numsSize, int k){
   k %= numsSize;
   reverse(nums, 0, numsSize - k - 1);
   reverse(nums, numsSize - k, numsSize - 1);
   reverse(nums, 0, numsSize - 1);
}

4.数组形式的整数加法

对于非负整数X而言,X的数组形式是每位数字按照从左到右的顺序形成的数组.例如,如果X = 1231,那么其数组形式为[1, 2, 3, 1]

给定非负整数X的数组形式A,返回整数X+K的数组形式

示例:输入:A = [1, 2, 0, 0], k = 34

输出:[1,2,3,4]

解释:1200 + 34 = 1234

int* addToArrayForm(int* A, int ASize, int k, int* returnSize){
   //获取数字K的长度
   int len = 0;
   int tmp = k;
   while (tmp){
       ++len;
       tmp /= 10;
   }
   //获取结果的最大长度
   int arrLen = len > ASize ? len + 1 : ASize + 1;
   int* ret = (int*)malloc(sizeof(int)* arrLen);

   //从个位开始相加
   int end = ASize - 1;
   //上一步进位
   int step = 0;
   int idx = 0;
   while (end >= 0 || k > 0){
       //每一位的结果包含了进位 + 对应位的值
       //首先加进位值
       int curRet = step;
       if (end >= 0)
           curRet += A[end];
       if (k > 0)
           curRet += k % 10;
       //处理进位
       if (curRet > 9){
           step = 1;
           curRet -= 10;
       }

else

step = 0;
       //保存当前位的结果:逆序存放
       ret[idx++] = curRet;
       //累加高位的值
       --end;
       k /= 10;
   }
   //判断最高位是否拥有进位
   if (step == 1)
       ret[idx++] = 1;
   //逆转
   int start = 0;
   end = idx - 1;
   while (start < end){
       int tmp = ret[start];
       ret[start] = ret[end];
       ret[end] = tmp;
       ++start;
       -- end;
   }
   //返回结果的长度
   *returnSize = idx;
   return ret;
}

链表

链表的结构非常多样,以下情况组合起来就有八种链表结构:

1.单向,双向

2.带头,不带头

3.循环,非循环

虽然有这么多的链表结构,但我们实际最常用的还是两种结构:

1.无头单向非循环链表:结构简单,一般不会单独存数据.实际中更多是作为其他数据结构的子结构,如哈希桶,图的邻接表等.笔试面试中出现较多.

2.带头双向循环链表

写单链表的一些接口(和上一博一样写头插头删尾插尾删查找销毁等...只不过上个是顺序表这个是单链表)

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

typedef int LDataType;
typedef struct listNode{
LDataType _data;
struct listNode* _next;
}listNode;

typedef struct list{
//存放第一个节点的地址
listNode* _head;
}list;

void listInit(list* lst){
   //初始化为空的链表
   if (lst == NULL)
       return;
   lst->_head = NULL;
}

listNode* creatNode(LDataType val){
   listNode* node = (listNode*)malloc(sizeof(listNode));
   node->_data = val;
   node->_next = NULL;
   return node;
}
//尾插
void listPushBack(list* lst,LDataType val){
   if (lst == NULL)
       return;
   //第一种空链表插入第一个数据
   if (lst->_head == NULL){
       //创建节点
       lst->_head = creatNode(val);
   }
   else{
       //遍历,找到最后一个节点
       listNode* tail = lst->_head;
       while (tail->_next != NULL){
           tail = tail->_next;
       }
       //插入
       tail->_next = creatNode(val);
   }

}
//尾删
void listPopBack(list* lst){

   if (lst == NULL || lst->_head == NULL)
       return;

   struct listNode* tail = lst->_head;
   struct listNode* prev = NULL;
   //遍历找到最后一个节点
   while (tail->_next != NULL){
       prev = tail;
       tail = tail->_next;
   }
   //删除节点
   free(tail);
   //修改指向
   if (prev = NULL) //删除的是头结点,更新头结点
       lst->_head = NULL;
   else
   prev->_next = NULL;
}

//头插
void listPushFront(list* lst, LDataType val){
   if (lst == NULL)
       return;
   //空的链表,插入第一个数据
   if (lst->_head == NULL)
       lst->_head = creatNode(val);
   else{
       listNode* node = creatNode(val);
       listNode* next = lst->_head;
       //head,node,next
       lst->_head = node;
       node->_next = next;
   }
}

//头删
void listPopFront(list* lst){
   if (lst == NULL || lst->_head == NULL)
       return;
   struct listNode* next = lst->_head->_next;
   //释放头结点
   free(lst->_head);
   lst->_head = next;
}

//中间位置的插入
void listInsertAfter(listNode* cur, LDataType val){
   listNode* node = creatNode(val);
   listNode* next = cur->_next;
   //cur node next
   cur->_next = node;
   node->_next = next;

}

//删除cur节点的下一个节点
void listEraseAfter(listNode* cur){
   //cur next next->next
   listNode* next = cur->_next;
   if (next == NULL)
       return;
   listNode* nextnext = cur->_next;
   free(next);
   cur->_next = nextnext;
}

listNode* listFind(list* lst, LDataType val){
       if (lst == NULL || lst->_head == NULL)
           return NULL;
       //从第一个节点开始遍历
       listNode* cur = lst->_head;
       while (cur){
           if (cur->_data == val)
               return cur;

           cur = cur->_next;
       }
       return NULL;
   }

void listDestory(list* lst){
   if (lst == NULL || lst->_head)
       return;
   //从第一个节点释放
   listNode* cur = lst->_head;
   while (cur){
       listNode* next = cur->_next;
       //释放节点
       free(cur);
       cur = next;
   }
   lst->_head = NULL;
}

void test(){
   list lst;
   listInit(&lst);
   listPushFront(&lst, 5);
   listPushFront(&lst, 4);
   listPushFront(&lst, 3);
   listPushFront(&lst, 2);
   listPushFront(&lst, 1);

listNode* cur = listFind(&lst, 3);
listInsertAfter(cur, 33);

cur = listFind(&lst, 2);
listEraseAfter(cur);
}

void listDestory(list* lst){

}
//void test(){
//   list lst;
//   listInit(&lst);
//   listPushBack(&lst, 1);
//   listPushBack(&lst, 2);
//   listPushBack(&lst, 3);
//   listPushBack(&lst, 4);
//   listPushBack(&lst, 5);
//
//   listPopBack(&lst);
//   listPopBack(&lst);
//   listPopBack(&lst);
//   listPopBack(&lst);
//   listPopBack(&lst);
//
//   listPushFront(&lst, 5);
//   listPushFront(&lst, 4);
//   listPushFront(&lst, 3);
//   listPushFront(&lst, 2);
//   listPushFront(&lst, 1);
//
//   listPopFront(&lst);
//   listPopFront(&lst);
//   listPopFront(&lst);
//   listPopFront(&lst);
//   listPopFront(&lst);
//}

int main(){

   test();
   system("pause");
   return 0;
}

原文地址:https://blog.csdn.net/2401_84919695/article/details/140287495 本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：https://www.suanlizi.com/kf/1810811675083935744.html 如若内容造成侵权/违法违规/事实不符，请联系《酸梨子》网邮箱：1419361763@qq.com进行投诉反馈，一经查实，立即删除！

阅读全部

24/07/09数据结构(3.1206)数组OJ单链表实现

相关推荐

最近更新

热门阅读